题解 | #基因变异最小次数# java

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param start string字符串
     * @param end string字符串
     * @param bank string字符串一维数组
     * @return int整型
     */
    public int minMutation (String start, String end, String[] bank) {
        // write code here
        Set<String> bankSet = new HashSet<>();
        for (String gene : bank) {
            bankSet.add(gene);
        }

        Queue<String> queue = new LinkedList<>();
        Set<String> visited = new HashSet<>();
        queue.offer(start);
        visited.add(start);
        int mutations = 0;

        while (!queue.isEmpty()) {
            int size = queue.size();

            for (int i = 0; i < size; i++) {
                String curr = queue.poll();

                if (curr.equals(end)) {
                    return mutations;
                }

                char[] currArray = curr.toCharArray();
                for (int j = 0; j < currArray.length; j++) {
                    char originalChar = currArray[j];

                    for (char c : new char[] {'A', 'C', 'G', 'T'}) {
                        currArray[j] = c;
                        String nextGene = new String(currArray);

                        if (bankSet.contains(nextGene) && !visited.contains(nextGene)) {
                            queue.offer(nextGene);
                            visited.add(nextGene);
                        }
                    }

                    currArray[j] = originalChar;
                }
            }

            mutations++;
        }

        return -1;
    }
}

Java语言编写代码

考察的是BFS。

代码的文字解释如下：

1. 变量bankSet用于存储基因库中的基因序列。
2. 将基因库中的基因序列添加到bankSet中。
3. 队列queue，用于广度优先搜索。
4. visited用于记录已经访问过的基因序列。
5. 将起始基因序列start加入队列queue和访问集合visited。
6. 初始化变异次数mutations为0。
7. 进入循环，直到队列为空。
8. 在每次循环开始时，获取当前队列的大小，用于控制内层循环的迭代次数。
9. 增加变异次数mutations。
10. 在内层循环中，依次取出队列中的基因序列。
11. 如果当前基因序列等于目标基因序列end，返回变异次数mutations，表示找到了最小变异次数。
12. 将当前基因序列转换成字符数组，并逐个修改其中的字符。
13. 如果修改后的基因序列在基因库中并且未被访问过，将其加入队列和访问集合。
14. 恢复当前基因序列到原始状态，并继续下一次循环。
15. 如果循环结束后都没有找到最小变异次数，则返回-1，表示无法完成基因变异。