LeetCode 433. 最小基因变化

约 6 分钟
文章信息 3 个分类 3 个标签
分类
LeetCode 中等 面试经典 150 题
标签
字符串 哈希表 广度优先搜索

题目描述

✅ 433. 最小基因变化

image-20260928233709935

image-20260928233709936

题意分析

基因序列是长度为八的字符串，每个位置只能是 A、C、G、T。从起始序列变到目标序列，每次恰好改变一个位置，且改变后的整个序列必须出现在基因库 bank 中，返回最少变化次数；无法到达时返回 -1。

起点默认合法，即使不在基因库中也可以开始。后续每个中间序列都必须合法，不能只比较起点与终点有多少处不同，因为需要的中间序列可能缺失，也可能必须绕路。若起点已经等于终点，则不需要变化。

解法：BFS 求最少单字符变化次数

核心思路

[!blue]

把起点和基因库中的不同字符串看成节点。若库中的候选与当前状态恰好有一个位置不同，就存在指向该候选的一次变化边。每条边都只花一次变化，因此最少变化次数就是无权图中从起点到终点的最短距离。

使用 BFS，从变化次数零的起点开始逐层扩展。先处理所有一步可达的状态，再处理两步可达的状态，以此类推。第一次取出目标时，更短距离的全部可能已经处理过，所以当前距离就是最少次数，不能用 DFS 首次遇到目标代替这个保证。

本题基因库很小，不必预先创建整张图。每处理一个基因，就扫描库中的候选，逐位置比较差异，选出恰好差一位的邻居。Java 在发现第二处差异时提前停止；它的 c > 0 也允许零处差异，但同一个字符串早已在访问集合中，因此实际新入队的仍只能是差一位的状态。

访问标记必须在入队时设置，而不是等出队再设置。同一个状态可能被本层多个节点发现，第一次发现已经具有最短距离，后续再入队只会重复工作。起点也先标记，避免从基因库绕回起点形成循环。

Java 用当前层固定的队列长度统一管理 depth；Go 在每个队列项中直接保存距离。两者都让新邻居比当前状态多一次变化。队列耗尽还未遇到目标，就说明所有可达合法状态已经检查完，返回失败。

解题步骤

  1. 将起点和距离零加入队列，并标记已访问。
  2. 取出状态，若等于目标，返回其变化次数。
  3. 扫描基因库，找出恰好相差一位且尚未访问的候选。
  4. 候选入队时立即标记，将其距离设为当前距离加一。
  5. 队列为空仍未找到目标时返回 -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{
        {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 + 1)mL)$，m 为基因库长度，L = 8。最多访问起点及库中的 m 个不同状态，每次扫描全部候选并比较至多 L 个字符。
  • 空间复杂度：$O(m + 1)$，队列和访问集合保存已发现的状态，基因长度固定。

关键点总结

[!green]

  • 合法序列构成状态图，单次变化代价相同，使 BFS 的层数等于最短距离。
  • 起点可不在库中，但生成后续状态时必须从库中选。
  • 首次入队就标记，避免重复发现改变队列规模或距离处理。

易错点总结

[!yellow]

  • 只计算起点与终点的字符差异数，无法保证对应中间状态都在基因库中。
  • 要求起点也必须出现在 bank，会错误排除题目允许的起始状态。
  • 出队后才设置访问标记，会让同一状态被多个父节点重复加入。
  • Java 处理当前层时不断读取增长后的队列长度，会把下一层节点混入当前深度。
  • 将零处差异也当作新的变化入队，会制造自环；现有 Java 实现由访问集合排除了这种情况。
  • 找到目标不代表所有搜索方法都得到最短距离，这里依赖 BFS 按距离递增的访问顺序。

相似题目

题目 难度 关联与区别
127. 单词接龙 困难 同样构建单字符变化图并求最短路，本题字符串长度固定且 bank 较小，直接扫描候选即可。
752. 打开转盘锁 中等 同样在有限状态空间按单位代价搜索，区别是邻居由密码锁操作生成而非扫描 bank。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/44549667
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！