Leetcode 最小基因变化

java solution：BFS 算法

class Solution {public int minMutation(String startGene, String endGene, String[] bank) {//首先创建一个集合来存储有效基因串Set<String> bankSet = new HashSet<>(Arrays.asList(bank));if(!bankSet.contains(endGene)) return -1;//初始化BFS所需的char[] genes = new char[]{'A', 'G', 'T', 'C'};Queue<String> queue = new LinkedList<>();queue.offer(startGene);Set<String> visited = new HashSet<>();visited.add(startGene);int steps = 0;while(!queue.isEmpty()) {int size = queue.size();for(int i = 0; i < size; i++) {String current = queue.poll();if(current.equals(endGene)) return steps;//将当前字符串转换为字符数组char [] currArray = current.toCharArray();for(int j = 0; j < currArray.length; j++) {char oldChar = currArray[j];for(char g : genes) {if(g == oldChar) continue;currArray[j] = g;String mutated = new String(currArray);if(bankSet.contains(mutated) && !visited.contains(mutated)) {queue.offer(mutated);visited.add(mutated);}}currArray[j] = oldChar; // 回溯}}steps++;}return -1;}
}

好的，我们来详细剖析这段 Java 代码，理解它的算法思想和执行流程。这其实是一个经典的 图搜索问题，问题背景是基因变换，但本质和图上的最短路径查找非常类似。

---

🧠 问题建模（算法思想）

🧬 核心问题描述：

我们从一个 start 基因串（字符串），每次只能变换一个字符（只允许变换为 A、C、G 或 T），且每次变换后的字符串必须在 bank 中出现过，最终希望变换到目标字符串 end，求最少变换次数。

---

🗺️ 算法模型（抽象为图）

• 每一个有效基因串是 图中的一个节点。
• 如果两个基因串只差一个字符，且变换后的串在 bank 中出现，那么这两个节点之间就有一条边。
• 要找的就是从 start 到 end 的 最短路径长度（经过的边数），这是典型的**BFS（广度优先搜索）**应用场景。

---

🛠️ Java 代码详细解析

Set<String> bankSet = new HashSet<>(Arrays.asList(bank));
if (!bankSet.contains(end)) return -1;

✅ 初始化阶段：

• 把基因库 bank 转成 Set，加快查询速度（O(1)）。
• 如果目标基因 end 不在 bank 中，那肯定到达不了，直接返回 -1。

---

char[] genes = new char[]{'A', 'C', 'G', 'T'};
Queue<String> queue = new LinkedList<>();
queue.offer(start);
Set<String> visited = new HashSet<>();
visited.add(start);
int steps = 0;

✅ 准备 BFS 所需的结构：

• genes：4 个可选的字符，便于构造变异。
• queue：BFS 队列，初始化时把 start 放进去。
• visited：避免重复访问，防止死循环。
• steps：当前已经变换的次数，代表路径长度。

---

while (!queue.isEmpty()) {int size = queue.size(); // 当前层有多少节点

✅ BFS 主体循环：

• 每一轮 BFS 相当于一次“变异”，我们遍历当前层所有节点（当前的字符串），进行下一步扩展。
• steps 就是变换次数，每一层就对应一次基因变换。

---

    for (int i = 0; i < size; i++) {String current = queue.poll();if (current.equals(end)) return steps;

• 从队列中取出当前处理的字符串 current。
• 如果已经变异成功（等于 end），返回当前的变异次数 steps。

---

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

• 遍历字符串中的每一个字符，尝试每个位置进行变异（一个字符变成另一个）。

---

            for (char g : genes) {if (g == oldChar) continue;currArray[j] = g;String mutated = new String(currArray);

• 尝试把当前字符换成 A/C/G/T 中的其他字符，形成一个新字符串 mutated。

---

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

• 如果这个变异后的字符串合法（在 bankSet 中，且没访问过），就放入队列，作为下一层搜索的起点。

---

            currArray[j] = oldChar; // 回溯，恢复原字符}}steps++; // 这一层结束，步数+1
}

• 每次外层 while 循环结束，表示进行了一次合法变异，steps++。

---

return -1; // 如果队列空了还没找到，说明变不了

---

✅ 算法时间复杂度分析

• 状态数：最多为 bank 中字符串个数（假设为 n）。
• 每个状态的扩展操作：每个字符最多有 3 种变异方式（A/C/G/T 中除了自己），所以最多 8 × 3 = 24 种尝试。
• 整体复杂度：O(n × m)，其中 n 是 bank 长度，m 是字符串长度（固定为 8）。

---

🧪 示例解释

以示例 2 为例：

start = "AACCGGTT"
end = "AAACGGTA"
bank = ["AACCGGTA","AACCGCTA","AAACGGTA"]

BFS 过程：

1. Start: "AACCGGTT" → "AACCGGTA"（step 1）
2. "AACCGGTA" → "AAACGGTA"（step 2）
   结果：最少变换次数是 2。

---

如果你还想了解：

• 用 DFS 解法解决这个问题？
• 如何构造图再用 Dijkstra 来做？
• 或是如何扩展到通用的字符串变换题（比如 Word Ladder）？

可以告诉我，我们可以进一步延伸～