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<>(Arrays.asList(
                                                bank)); // 将基因库转换为集合
        Queue<String> q = new LinkedList<>();
        Set<String> visited = new HashSet<>();
        q.offer(start);
        visited.add(start);
        int mutations = 0; // 变化次数

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

            for (int i = 0; i < size; ++i) {
                String curr = q.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; // 尝试将当前字符变成 'A'、'C'、'G' 和 'T'
                        String newString = new String(currArray);

                        // 判断变化后的基因序列是否在基因库中且未被访问过
                        if (bankSet.contains(newString) && !visited.contains(newString)) {
                            q.offer(newString); // 将变化后的基因序列加入队列
                            visited.add(newString); // 标记为已访问
                        }
                    }

                    currArray[j] = originalChar; // 恢复当前字符
                }
            }

            mutations++; // 增加变化次数
        }

        return -1; // 无法完成基因变化，返回 -1
    }
}

代码使用的是Java语言。

该题考察的知识点是使用广度优先搜索（BFS）解决问题。BFS是一种图遍历算法，它从给定的起始节点开始，逐层地向外扩展搜索，直到找到目标节点或搜索完整个图。在这道题中，我们将基因序列看作是一个图，每个基因序列为图中的一个节点，两个基因序列之间如果只有一个字符不同，那么它们之间存在一条边。

代码的文字解释如下：

1. 集合 visited，用于记录已经访问过的基因序列。
2. 将起始基因序列 start 放入队列 q 中，并将其标记为已经访问过。
3. 使用变量 mutations 记录当前的变化次数，初始化为0。
4. 进入主循环，判断队列 q 是否为空。如果不为空，则继续进行下一轮的遍历。
5. 在每一轮中首先获取当前队列中的基因序列数量，以保证每一轮只处理当前层的节点。
6. 对于当前队列中的每个基因序列，将每个位置的字符尝试替换为 'A'、'C'、'G'、'T'。
7. 对于每一种替换后的情况，判断变化后的基因序列是否在基因库中且未被访问过。如果满足条件，则将其放入队列 q 中，并将其标记为已经访问过。
8. 在尝试完所有可能的替换后，恢复当前字符，进行下一轮的替换操作。
9. 每完成一轮遍历，增加变化次数 mutations。
10. 如果在遍历的过程中找到了目标基因序列 end，则直接返回当前变化次数 mutations。
11. 如果遍历结束仍未找到目标基因序列，则返回 -1，表示无法完成基因变化。