LeetCode 433. 最小基因变化

2026-03-28 HGNULB 约 12 分钟

文章信息 3 个分类 4 个标签

分类

题目描述

✅ 433. 最小基因变化

题意分析

题目目标：基因串是长度为 8、字符取自 A/C/G/T 的字符串。一次变化只能改动一个字符，且变化后的串必须出现在基因库 bank 中。求从 startGene 变到 endGene 的最少变化次数，无法到达返回 -1。

核心约束：三条约束共同决定了算法。第一，每次只改一个字符 → 两个串之间「相邻」的定义是汉明距离为 1。第二，中间产物必须在 bank 里 → 图的顶点集是 bank（加上起点），而不是全部 $4^8$ 种串。第三，求「最少变化次数」且每次变化代价相同 → 边权全为 1 的无权图最短路，BFS 是标准答案，不需要优先队列。

边界处理：endGene 可能不在 bank 里，此时必然无解（除非它恰好等于 startGene）；startGene 本身不要求在 bank 里，所以不能拿 bank 的成员资格当作起点的前提；startGene == endGene 时答案是 0；bank 可能为空。

实现取舍：邻居的生成方式有两种。一是「从 bank 里挑」——拿当前串与 bank 的每个串比一遍汉明距离，单次 $O(mL)$；二是「主动构造」——对 8 个位置各尝试换成另外 3 个字符，得到 24 个候选再查 bank 是否包含，单次 $O(L \cdot 4 \cdot L)$。本题 bank 长度不超过 10，两者都很快，第一种写法更短。

解法：哈希表统计状态

核心思路

先把题目翻译成图论语言：顶点是基因串，边连接汉明距离为 1 的两个串，求 startGene 到 endGene 的最短路径长度。一旦完成这次翻译，剩下的就是把 BFS 模板套上去，难点只剩「顶点集怎么定」和「访问标记什么时候打」。

顶点集只能是 bank 加起点。这是因为题目规定每次变化后的串必须出现在 bank 中——换句话说，bank 之外的串是不存在的中间态，哪怕它离终点只差一步。很多人第一反应是「枚举所有 $4^8 = 65536$ 种串建图」，那是在解一道更难的题，且忽略了题目给的强约束。

为什么用 BFS 而不是 DFS 或 Dijkstra：每次变化的代价都是 1，边权相同，BFS 的层数天然就是最短距离；DFS 找到的第一条路径不保证最短，还要遍历全部路径才能取最小；Dijkstra 在等权图上退化成 BFS，白白多一个堆。

不变量写清楚：队列中同一层的所有基因串，到起点的最短变化次数相同，等于当前的 depth。代码用「按层扩展」的写法——外层循环开始时先记下队列大小 m，然后恰好弹出 m 个元素作为一层，处理完这一层再 ++depth。这样 depth 与层号严格对应，不需要给每个元素单独存距离（Go 版则选择了另一种等价写法：把 depth 打包进队列元素，两种写法二选一即可）。

访问标记必须在入队时打，而不是出队时。理由是：同一层里可能有多个串都能变到同一个邻居，若等到出队才标记，这个邻居会被重复入队多次，队列规模可能指数膨胀。入队即标记保证每个串最多进队一次，总工作量才有界。

最后是终止判断的位置。代码在出队时检查是否等于 endGene，而不是在入队时检查。这个选择的好处是自动处理了 startGene == endGene 的情形——起点在第 0 层出队时立刻命中，返回 0；若放在入队时判断，起点从未经过「入队检查」这一步，会漏掉这个边界。

解题步骤

第一步：起点入队，同时放进 vis 集合，depth = 0。 为什么起点也要标记：否则某条路径可能绕回起点，造成重复展开甚至死循环。

第二步：外层 while 每轮处理一整层。进入时先取 m = q.size()，然后循环恰好 m 次。 为什么要先取出大小再循环：循环体内会往队列里追加下一层的元素，如果直接用 q.size() 作为循环条件，新元素会混进当前层，depth 与实际距离脱钩。

第三步：出队一个基因串，若等于 endGene，立即返回 depth。 为什么此时返回的一定是最短：由不变量，出队元素所在层号就是它到起点的最短距离，而 BFS 逐层推进，第一次遇到终点必然是最短路。

第四步：遍历 bank 中每个候选 next，统计它与当前串的字符差异个数。 代码用一个从 2 开始递减的计数器 c：每遇到一个不同字符就 --c，一旦 c 归零就靠循环条件 c > 0 提前退出。为什么这样写：我们只关心「差异是否 ≤ 1」，差异数超过 1 之后继续比较毫无意义，提前退出省掉无谓的字符比较。循环结束后 c > 0 即等价于「差异不超过 1」。

第五步：c > 0 && !vis.contains(next) 时把 next 入队并立刻标记。 为什么差异为 0 的情形不需要额外排除：差异为 0 意味着 next 就是当前串本身，而当前串已经在 vis 里（入队时就标记了），第二个条件会把它挡掉。

第六步：一层处理完毕后 ++depth；队列耗尽仍未命中终点，返回 -1。 为什么队列耗尽就等于无解：BFS 会访问到起点连通分量内的全部顶点，走不到终点说明它们根本不连通。

以 startGene = "AACCGGTT"、endGene = "AAACGGTA"、bank = ["AACCGGTA", "AACCGCTA", "AAACGGTA"] 走一遍：

初始队列 ["AACCGGTT"]，vis = {"AACCGGTT"}，depth = 0。

第 0 层：出队 "AACCGGTT"，不等于终点。逐个考察 bank：与 "AACCGGTA" 只在第 7 位（T vs A）不同，差异 1，未访问 → 入队并标记；与 "AACCGCTA" 在第 5 位（G vs C）和第 7 位（T vs A）都不同，计数器减到 0 后提前退出，c = 0 被拒；与 "AAACGGTA" 在第 2 位（C vs A）和第 7 位不同，同样被拒。这一层结束，depth 变成 1，队列是 ["AACCGGTA"]。

第 1 层：层大小为 1。出队 "AACCGGTA"，不等于终点 "AAACGGTA"（注意这两个串很像，只差第 2 位与第 3 位的排布，实际差异为 2 位）。考察 bank："AACCGGTA" 是自己且已在 vis，被第二个条件挡掉；与 "AACCGCTA" 只在第 5 位不同，差异 1 → 入队标记；与 "AAACGGTA" 只在第 2 位不同，差异 1 → 入队标记。这一层结束，depth 变成 2，队列是 ["AACCGCTA", "AAACGGTA"]。

第 2 层：层大小为 2。先出队 "AACCGCTA"，不是终点，它的邻居要么已访问要么差异过大，不产生新元素；再出队 "AAACGGTA"，等于 endGene，返回当前 depth = 2。

验证：AACCGGTT → AACCGGTA → AAACGGTA，两次变化，每次只改一个字符，且中间产物都在 bank 中，与期望一致。

再看无解用例 startGene = "AACCGGTT"、endGene = "AACCGGTA"、bank = []：起点入队后第 0 层出队，不等于终点，bank 为空没有任何邻居可入队；这一层结束后队列已空，while 退出，返回 -1，正确。

代码实现

class Solution {
    public int minMutation(String startGene, String endGene, String[] bank) {
        Deque<String> q = new ArrayDeque<>();
        q.offer(startGene);
        Set<String> vis = new HashSet<>();
        vis.add(startGene);
        int depth = 0;
        while (!q.isEmpty()) {
            for (int m = q.size(); m > 0; --m) {
                String gene = q.poll();
                if (gene.equals(endGene)) {
                    return depth;
                }
                for (String next : bank) {
                    int c = 2;
                    for (int k = 0; k < 8 && c > 0; ++k) {
                        if (gene.charAt(k) != next.charAt(k)) {
                            --c;
                        }
                    }
                    if (c > 0 && !vis.contains(next)) {
                        q.offer(next);
                        vis.add(next);
                    }
                }
            }
            ++depth;
        }
        return -1;
    }
}

func minMutation(startGene string, endGene string, bank []string) int {
    type pair struct {
        s     string
        depth int
    }
    q := []pair{pair{startGene, 0}}
    vis := map[string]bool{startGene: true}
    for len(q) > 0 {
        p := q[0]
        q = q[1:]
        if p.s == endGene {
            return p.depth
        }
        for _, next := range bank {
            diff := 0
            for i := 0; i < len(startGene); i++ {
                if p.s[i] != next[i] {
                    diff++
                }
            }
            if diff == 1 && !vis[next] {
                vis[next] = true
                q = append(q, pair{next, p.depth + 1})
            }
        }
    }
    return -1
}

复杂度分析

时间复杂度：$O(m^2 L)$，其中 $m$ 是 bank 的长度、$L = 8$ 是基因串长度。凭什么：由于入队即标记，每个基因串最多出队一次，共 $O(m)$ 次；每次出队都要把 bank 扫一遍（$m$ 个候选），每个候选比较至多 $L$ 个字符。本题 $m \le 10$，实际运算量极小。

空间复杂度：$O(m)$。凭什么：vis 集合与队列各自最多容纳 $m + 1$ 个基因串（bank 全部加起点），每个串长度固定为 8 视作常数；没有递归栈。

关键点总结

看到「每步代价相同 + 求最少步数」就锁定 BFS。 边权等值是 BFS 层数等于最短距离的唯一前提，一旦代价不等（如迷宫滚动、带权图）必须换 Dijkstra。

顶点集由题目约束决定，不要自作主张扩大。 本题的中间态必须在 bank 里，枚举全部 $4^8$ 种串是在解一道不存在的题。

访问标记必须在入队时打，不能等到出队。 出队才标记会让同一层的多个前驱重复入队，队列规模失控，这是 BFS 最常见的性能陷阱。

终止判断放在出队处，可以顺手兼容「起点即终点」。 放在入队处会漏掉起点自身，需要额外特判。

按层扩展时先固化层大小。 for (int m = q.size(); m > 0; --m) 这个写法把当前层与下一层隔开，是 depth 语义正确的保证。

面试视角：先把题目显式翻译成「无权图最短路」，说明顶点、边、起终点分别是什么，再套 BFS 模板。写完主动提两个优化：一是可以先把 bank 放进哈希集合，然后主动构造 24 个邻居候选（$L \times 3$）并 $O(1)$ 查表，当 bank 很大时优于两两比较；二是可以用双向 BFS 从起点和终点同时扩展，把搜索规模从 $b^d$ 降到 $2b^{d/2}$。这两句是本题和 127 题的通用加分点。

易错点总结

错误写法：出队时才把元素加入 vis → 用例 startGene = "AACCGGTT"、bank = ["AACCGGTA", "AACCGCTA", "AAACGGTA"]，第 1 层的 "AACCGGTA" 会把 "AACCGCTA" 和 "AAACGGTA" 各入队，而它们彼此又互为距离 2 不产生重复；但换成 bank 中存在多个到同一邻居距离为 1 的串时，该邻居会被重复入队，队列规模成倍增长，大数据下超时。

错误写法：忘记把 startGene 放进 vis → 用例 bank 中恰好包含 startGene 时，起点会被自己的邻居重新入队，depth 多算一层甚至陷入起点与邻居之间的来回震荡。

错误写法：层循环写成 for (int m = 0; m < q.size(); ++m) → 用例 bank = ["AACCGGTA", "AACCGCTA", "AAACGGTA"]，q.size() 在循环中随着入队不断变大，当前层与下一层混在一起，depth 只增加一次，返回值恒为 1 或 0。

错误写法：在入队时判断是否等于 endGene 并返回 depth + 1 → 用例 startGene == endGene，起点从未走过入队判断，队列耗尽后返回 -1，而期望是 0。

错误写法：差异计数写成 c 从 1 开始递减、条件为 c >= 0 → 用例 gene = "AACCGGTT"、next = "AACCGCTA"（差异 2），第一次不同后 c 变 0，循环条件 c >= 0 仍成立，第二次不同后 c 变 -1，最终 c >= 0 为假被正确拒绝；但若把最终判断也写成 c >= 0，差异为 2 的串会在 c = 0 时被误判为合法邻居，得到偏小的答案。

错误写法：Go 版把 diff == 1 写成 diff <= 1 且没有 vis 保护 → 用例任意，diff == 0 表示自己，会把当前串重新入队，depth 无限增长直到内存耗尽。

错误写法：假定 endGene 一定在 bank 中而提前 return -1 做剪枝，却漏了 startGene == endGene → 用例 startGene = endGene = "AACCGGTT"、bank = []，剪枝直接返回 -1，期望 0。

错误写法：把顶点集扩大为全部 $4^8$ 种基因串，忽略「中间产物必须在 bank 中」 → 用例 bank = ["AAACGGTA"]、startGene = "AACCGGTT"、endGene = "AAACGGTA"，两串差异为 2，真实答案是 -1（没有合法中间态），但按全串图搜索会找到一条经过 bank 外中间串的路径返回 2。

错误写法：用 DFS 递归求解并返回第一条到达终点的路径长度 → 用例存在多条路径时，先探到的未必最短，返回值偏大；要正确必须遍历所有路径取最小，复杂度爆炸。

错误写法：字符比较循环的上界写成 k < gene.length() 但 bank 中混有长度不同的串（自造测试数据时） → next.charAt(k) 越界抛异常；本题保证长度均为 8，但迁移到 127 题时单词长度由输入决定，必须用变量而非硬编码。

相似题目

题目	难度	考察点
127. 单词接龙	困难	词表规模大到无法两两比较，需要用通配符桶建立邻接关系，且返回的是节点数而非边数
542. 01 矩阵	中等	多源 BFS：把所有 0 一次性入队作为第 0 层
752. 打开转盘锁	中等	邻居由每位数字正反转动产生，还要把死亡列表并入访问集合
773. 滑动谜题	困难	状态是整个棋盘排列，需要序列化成字符串才能放进访问集合
854. 相似度为 K 的字符串	困难	邻居由交换两个位置产生，必须只交换第一个失配位来剪枝，否则分支数爆炸
909. 蛇梯棋	中等	顶点是编号而非字符串，邻居来自骰子的 1~6 步跳跃并叠加蛇梯传送
994. 腐烂的橘子	中等	多源 BFS 且结束后要回扫是否仍有未腐烂的橘子来决定返回 -1
1091. 二进制矩阵中的最短路径	中等	邻居是八方向而非四方向，且起点终点自身可能是障碍
1129. 颜色交替的最短路径	中等	状态需要扩维记录「上一条边的颜色」，同一个点会被访问两次
1162. 地图分析	中等	多源 BFS 但求的是最大距离，答案取最后一层的层号
1293. 网格中的最短路径	困难	状态扩维记录剩余可消除障碍数，访问标记是三维的
1298. 你能从盒子里获得的最大糖果数	困难	顶点之间存在钥匙依赖，拿到新钥匙后要回头重新检查此前打不开的盒子
1345. 跳跃游戏 IV	困难	同值下标互为邻居，展开一次后必须清空该值的邻接表，否则退化成 $O(n^2)$
1654. 到家的最少跳跃次数	中等	前进与后退不对称，状态要带「上一步是否后退」，还需自行推导搜索上界
LCP 09. 最小跳跃次数	困难	回退边数量巨大，需要维护「已访问的最右前缀」把这类边压成均摊 $O(1)$
LCR 107. 01 矩阵	中等	专题版同题，适合对照「两次方向扫描的动态规划」这一非 BFS 解法
LCR 108. 单词接龙	困难	专题版同题，适合练双向 BFS 的实现细节
LCR 109. 打开转盘锁	中等	专题版同题，适合练双向 BFS 中两侧集合何时交换、何时判交