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 过程：
- Start:
"AACCGGTT"→"AACCGGTA"（step 1） "AACCGGTA"→"AAACGGTA"（step 2）
结果：最少变换次数是 2。
如果你还想了解：
- 用 DFS 解法解决这个问题？
- 如何构造图再用 Dijkstra 来做？
- 或是如何扩展到通用的字符串变换题（比如 Word Ladder）？
可以告诉我，我们可以进一步延伸～