题解 | #基因变异最小次数# 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) {
        Set<String> bankSet = new HashSet<>(Arrays.asList(
                                                bank)); // 将基因库转换为哈希集合
        Queue<String> q = new LinkedList<>();
        Set<String> visited = new HashSet<>();
        q.add(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[] currChars = curr.toCharArray();
                for (int j = 0; j < currChars.length; ++j) {
                    char originalChar = currChars[j];

                    for (char c : new char[] {'A', 'C', 'G', 'T'}) {
                        currChars[j] = c; // 尝试将当前字符变成 'A'、'C'、'G' 和 'T'
                        String transformed = new String(currChars);

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

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

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

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

编程语言是Java。

该题考察的知识点包括：

• 广度优先搜索（BFS）：使用队列实现广度优先搜索，寻找从起始基因到目标基因的最短变异路径。
• 集合（Set）的使用：将基因库转换为集合，以便快速查找基因是否在库中。
• 字符串处理：在基因的不同位置尝试替换字符，生成新的基因，并进行查找和比较。

文字解释：从起始基因开始，逐步尝试将每个位置的字符替换为 'A'、'C'、'G' 和 'T'，生成新的可能的变异基因，并查找是否在基因库中。如果找到了目标基因，则返回变异次数；否则，继续尝试下一轮变异。最终，如果无法找到从起始基因到目标基因的变异路径，则返回 -1 表示无法完成变异。