LeetCode 433中等图搜索

最小基因变化图解题解

这道题到底在问什么

基因由 A C G T 组成，长 8。每次变化只改 1 个字符，且变化后的基因必须出现在基因库 bank 中。求从 start 变到 end 的最少变化次数，无法到达返回 -1。

输入: start=AACCGGTT, end=AACCGCTA bank=[AACCGGTA,AACCGCTA,AAACGGTA,AACGGGTA,AAGCGGTA]
输出: 2

最优解：一步一步想明白

3记住三种颜色：紫=正在访问（刚出队）、蓝=已入队待处理、绿=已访问完。队列先进先出，保证按层扩展，最短路径天然得到。
4先把 6 个基因全摆上：点=基因，两基因只差一个字母就连边。还没开始搜，全是灰的，队列是空的。
5起点 AACCGGTT 入队，记它在第 ① 层（自己到自己 0 次变化，层号从 1 起算）。队列：[AACCGGTT]。
6从队头取出 AACCGGTT（标紫=正在访问），它在第 ① 层。逐个看它能一步变成哪些库里的基因。
7AACCGGTT 改一个字母得到 AACCGGTA（库里有、没访问过），层号 = ① 的层 +1 = ②，入队。队列：[AACCGGTA]。
8AACCGGTT 的相邻基因都看完了，把它标绿=已访问。继续从队头取下一个。
9从队头取出 AACCGGTA（标紫=正在访问），它在第 ② 层。逐个看它能一步变成哪些库里的基因。
10AACCGGTA 改一个字母得到 AACCGCTA，正是目标 end！层号 = ② 的层 +1 = ③，入队。第一次碰到 end，最少变化次数就锁定 = 层号-1 = 2。
11AACCGGTA 改一个字母得到 AAACGGTA（库里有、没访问过），层号 = ② 的层 +1 = ③，入队。队列：[AACCGCTA, AAACGGTA]。
12AACCGGTA 改一个字母得到 AACGGGTA（库里有、没访问过），层号 = ② 的层 +1 = ③，入队。队列：[AACCGCTA, AAACGGTA, AACGGGTA]。
13AACCGGTA 改一个字母得到 AAGCGGTA（库里有、没访问过），层号 = ② 的层 +1 = ③，入队。队列：[AACCGCTA, AAACGGTA, AACGGGTA, AAGCGGTA]。
14AACCGGTA 的相邻基因都看完了，把它标绿=已访问。继续从队头取下一个。
15从队头取出 AACCGCTA（标紫=正在访问），它在第 ③ 层。逐个看它能一步变成哪些库里的基因。
16AACCGCTA 也能一步变成 AACCGGTA，但 AACCGGTA 已经访问过/正在访问，跳过（BFS 每个点只处理一次）。
17AACCGCTA 的相邻基因都看完了，把它标绿=已访问。继续从队头取下一个。
18从队头取出 AAACGGTA（标紫=正在访问），它在第 ③ 层。逐个看它能一步变成哪些库里的基因。
19AAACGGTA 也能一步变成 AACCGGTA，但 AACCGGTA 已经访问过/正在访问，跳过（BFS 每个点只处理一次）。
20AAACGGTA 也能一步变成 AAGCGGTA，但 AAGCGGTA 已经在队列里（更早入队），不重复入队。
21AAACGGTA 的相邻基因都看完了，把它标绿=已访问。继续从队头取下一个。
22从队头取出 AACGGGTA（标紫=正在访问），它在第 ③ 层。逐个看它能一步变成哪些库里的基因。
23AACGGGTA 也能一步变成 AACCGGTA，但 AACCGGTA 已经访问过/正在访问，跳过（BFS 每个点只处理一次）。
24AACGGGTA 的相邻基因都看完了，把它标绿=已访问。继续从队头取下一个。
25从队头取出 AAGCGGTA（标紫=正在访问），它在第 ③ 层。逐个看它能一步变成哪些库里的基因。
26AAGCGGTA 也能一步变成 AACCGGTA，但 AACCGGTA 已经访问过/正在访问，跳过（BFS 每个点只处理一次）。
27AAGCGGTA 也能一步变成 AAACGGTA，但 AAACGGTA 已经访问过/正在访问，跳过（BFS 每个点只处理一次）。
28AAGCGGTA 的相邻基因都看完了，把它标绿=已访问。继续从队头取下一个。
29整张图按层扩完。最短变化链：AACCGGTT → AACCGGTA → AACCGCTA，相邻两基因都只差一个字母（一条边）。从起点到 end 共 2 条边，所以最少变化次数 = 2。

⚠️ 容易写错的地方

✗ 错：用 DFS 找路径

✓ 对：用 BFS 按层扩展

DFS 找到的不一定是最短；BFS 第一次到达 end 就是最少变化次数

✗ 错：忘了判断 end 是否在 bank 里

✓ 对：开头先查 end ∈ bank，否则直接返回 -1

变化后必须落在库里，end 不在库里则永远无法合法到达

✗ 错：不记 seen，重复访问

✓ 对：入队前标记已访问

同一基因被多次入队会指数级膨胀，且可能在更深的层重复处理

完整代码（Python / C++ / Java）

Python

from collections import deque
def minMutation(start, end, bank):
    bank = set(bank)
    if end not in bank: return -1        # 终点必须在库里
    q = deque([(start, 0)]); seen = {start}
    while q:
        gene, step = q.popleft()
        if gene == end: return step        # 按层，第一次到即最短
        for i in range(len(gene)):         # 改每一位
            for c in 'ACGT':
                nxt = gene[:i] + c + gene[i+1:]
                if nxt in bank and nxt not in seen:
                    seen.add(nxt); q.append((nxt, step + 1))
    return -1                             # 搜空也没到，无解

C++

int minMutation(string start, string end, vector<string>& bank){
    unordered_set<string> b(bank.begin(), bank.end());
    if(!b.count(end)) return -1;
    queue<pair<string,int>> q; q.push({start,0});
    unordered_set<string> seen{start};
    string g; int step;
    while(!q.empty()){
        tie(g,step)=q.front(); q.pop();
        if(g==end) return step;
        for(int i=0;i<(int)g.size();i++){
            char old=g[i];
            for(char c: {'A','C','G','T'}){
                g[i]=c; string nx=g;
                if(b.count(nx)&&!seen.count(nx)){ seen.insert(nx); q.push({nx,step+1}); }
            }
            g[i]=old;
        }
    }
    return -1;
}

Java

public int minMutation(String start, String end, String[] bank){
    Set<String> b = new HashSet<>(Arrays.asList(bank));
    if(!b.contains(end)) return -1;
    Queue<String> q = new LinkedList<>(); q.offer(start);
    Set<String> seen = new HashSet<>(); seen.add(start);
    int step = 0; char[] gene4 = {'A','C','G','T'};
    while(!q.isEmpty()){
        for(int sz=q.size(); sz>0; sz--){
            String g = q.poll();
            if(g.equals(end)) return step;
            char[] arr = g.toCharArray();
            for(int i=0;i<arr.length;i++){
                char old=arr[i];
                for(char c: gene4){
                    arr[i]=c; String nx=new String(arr);
                    if(b.contains(nx)&&!seen.contains(nx)){ seen.add(nx); q.offer(nx); }
                }
                arr[i]=old;
            }
        }
        step++;
    }
    return -1;
}

复杂度

时间

O(N·L·4)

N=库里基因数，每个基因有 L=8 位、每位试 4 种字母去匹配库

空间

O(N)

队列和已访问集合最多装下库里全部基因

看不够？换成动画再走一遍

上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着最小基因变化的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。

看交互动画版 →更多图解题

面试官可能追问

为什么这题用 BFS 而不是 DFS？+

要的是「最少变化次数」=无权图最短路径。BFS 按层扩展，第一次到 end 即最短；DFS 找到的路径不保证最短，还得遍历所有路径再取最小，更慢。

如何枚举一个基因的所有合法邻居？+

对它的每一位（共 8 位），分别试着改成 A C G T 四种字母，得到的新串若在 bank 里、且没访问过，就是一个合法邻居。也可以反过来：直接遍历 bank，挑出和当前基因恰好差一位的。

能不能用双向 BFS 优化？+

可以。同时从 start 和 end 两端往中间扩，哪端队列小就扩哪端，两端相遇即得答案，能把搜索空间从近似 b^d 降到 2·b^(d/2)，对深度大的图更快。

想听吴师兄把这道题讲给你听？

文字版和动画都随便看。开通图解算法年卡，可以听吴师兄把最小基因变化一步步讲透（全站已上线 905 份讲透，持续扩充），卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。

了解年卡方案 →先去动画页看完整样板 →

把这道题真正拿下

看动画图解 →最小基因变化交互动画,逐步看清每一步怎么走

本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。

LeetCode 433中等图搜索

最小基因变化图解题解

这道题到底在问什么

基因由 A C G T 组成，长 8。每次变化只改 1 个字符，且变化后的基因必须出现在基因库 bank 中。求从 start 变到 end 的最少变化次数，无法到达返回 -1。

输入: start=AACCGGTT, end=AACCGCTA bank=[AACCGGTA,AACCGCTA,AAACGGTA,AACGGGTA,AAGCGGTA]
输出: 2

最优解：一步一步想明白

3记住三种颜色：紫=正在访问（刚出队）、蓝=已入队待处理、绿=已访问完。队列先进先出，保证按层扩展，最短路径天然得到。
4先把 6 个基因全摆上：点=基因，两基因只差一个字母就连边。还没开始搜，全是灰的，队列是空的。
5起点 AACCGGTT 入队，记它在第 ① 层（自己到自己 0 次变化，层号从 1 起算）。队列：[AACCGGTT]。
6从队头取出 AACCGGTT（标紫=正在访问），它在第 ① 层。逐个看它能一步变成哪些库里的基因。
7AACCGGTT 改一个字母得到 AACCGGTA（库里有、没访问过），层号 = ① 的层 +1 = ②，入队。队列：[AACCGGTA]。
8AACCGGTT 的相邻基因都看完了，把它标绿=已访问。继续从队头取下一个。
9从队头取出 AACCGGTA（标紫=正在访问），它在第 ② 层。逐个看它能一步变成哪些库里的基因。
10AACCGGTA 改一个字母得到 AACCGCTA，正是目标 end！层号 = ② 的层 +1 = ③，入队。第一次碰到 end，最少变化次数就锁定 = 层号-1 = 2。
11AACCGGTA 改一个字母得到 AAACGGTA（库里有、没访问过），层号 = ② 的层 +1 = ③，入队。队列：[AACCGCTA, AAACGGTA]。
12AACCGGTA 改一个字母得到 AACGGGTA（库里有、没访问过），层号 = ② 的层 +1 = ③，入队。队列：[AACCGCTA, AAACGGTA, AACGGGTA]。
13AACCGGTA 改一个字母得到 AAGCGGTA（库里有、没访问过），层号 = ② 的层 +1 = ③，入队。队列：[AACCGCTA, AAACGGTA, AACGGGTA, AAGCGGTA]。
14AACCGGTA 的相邻基因都看完了，把它标绿=已访问。继续从队头取下一个。
15从队头取出 AACCGCTA（标紫=正在访问），它在第 ③ 层。逐个看它能一步变成哪些库里的基因。
16AACCGCTA 也能一步变成 AACCGGTA，但 AACCGGTA 已经访问过/正在访问，跳过（BFS 每个点只处理一次）。
17AACCGCTA 的相邻基因都看完了，把它标绿=已访问。继续从队头取下一个。
18从队头取出 AAACGGTA（标紫=正在访问），它在第 ③ 层。逐个看它能一步变成哪些库里的基因。
19AAACGGTA 也能一步变成 AACCGGTA，但 AACCGGTA 已经访问过/正在访问，跳过（BFS 每个点只处理一次）。
20AAACGGTA 也能一步变成 AAGCGGTA，但 AAGCGGTA 已经在队列里（更早入队），不重复入队。
21AAACGGTA 的相邻基因都看完了，把它标绿=已访问。继续从队头取下一个。
22从队头取出 AACGGGTA（标紫=正在访问），它在第 ③ 层。逐个看它能一步变成哪些库里的基因。
23AACGGGTA 也能一步变成 AACCGGTA，但 AACCGGTA 已经访问过/正在访问，跳过（BFS 每个点只处理一次）。
24AACGGGTA 的相邻基因都看完了，把它标绿=已访问。继续从队头取下一个。
25从队头取出 AAGCGGTA（标紫=正在访问），它在第 ③ 层。逐个看它能一步变成哪些库里的基因。
26AAGCGGTA 也能一步变成 AACCGGTA，但 AACCGGTA 已经访问过/正在访问，跳过（BFS 每个点只处理一次）。
27AAGCGGTA 也能一步变成 AAACGGTA，但 AAACGGTA 已经访问过/正在访问，跳过（BFS 每个点只处理一次）。
28AAGCGGTA 的相邻基因都看完了，把它标绿=已访问。继续从队头取下一个。
29整张图按层扩完。最短变化链：AACCGGTT → AACCGGTA → AACCGCTA，相邻两基因都只差一个字母（一条边）。从起点到 end 共 2 条边，所以最少变化次数 = 2。

⚠️ 容易写错的地方

✗ 错：用 DFS 找路径

✓ 对：用 BFS 按层扩展

DFS 找到的不一定是最短；BFS 第一次到达 end 就是最少变化次数

✗ 错：忘了判断 end 是否在 bank 里

✓ 对：开头先查 end ∈ bank，否则直接返回 -1

变化后必须落在库里，end 不在库里则永远无法合法到达

✗ 错：不记 seen，重复访问

✓ 对：入队前标记已访问

同一基因被多次入队会指数级膨胀，且可能在更深的层重复处理

完整代码（Python / C++ / Java）

Python

from collections import deque
def minMutation(start, end, bank):
    bank = set(bank)
    if end not in bank: return -1        # 终点必须在库里
    q = deque([(start, 0)]); seen = {start}
    while q:
        gene, step = q.popleft()
        if gene == end: return step        # 按层，第一次到即最短
        for i in range(len(gene)):         # 改每一位
            for c in 'ACGT':
                nxt = gene[:i] + c + gene[i+1:]
                if nxt in bank and nxt not in seen:
                    seen.add(nxt); q.append((nxt, step + 1))
    return -1                             # 搜空也没到，无解

C++

int minMutation(string start, string end, vector<string>& bank){
    unordered_set<string> b(bank.begin(), bank.end());
    if(!b.count(end)) return -1;
    queue<pair<string,int>> q; q.push({start,0});
    unordered_set<string> seen{start};
    string g; int step;
    while(!q.empty()){
        tie(g,step)=q.front(); q.pop();
        if(g==end) return step;
        for(int i=0;i<(int)g.size();i++){
            char old=g[i];
            for(char c: {'A','C','G','T'}){
                g[i]=c; string nx=g;
                if(b.count(nx)&&!seen.count(nx)){ seen.insert(nx); q.push({nx,step+1}); }
            }
            g[i]=old;
        }
    }
    return -1;
}

Java

public int minMutation(String start, String end, String[] bank){
    Set<String> b = new HashSet<>(Arrays.asList(bank));
    if(!b.contains(end)) return -1;
    Queue<String> q = new LinkedList<>(); q.offer(start);
    Set<String> seen = new HashSet<>(); seen.add(start);
    int step = 0; char[] gene4 = {'A','C','G','T'};
    while(!q.isEmpty()){
        for(int sz=q.size(); sz>0; sz--){
            String g = q.poll();
            if(g.equals(end)) return step;
            char[] arr = g.toCharArray();
            for(int i=0;i<arr.length;i++){
                char old=arr[i];
                for(char c: gene4){
                    arr[i]=c; String nx=new String(arr);
                    if(b.contains(nx)&&!seen.contains(nx)){ seen.add(nx); q.offer(nx); }
                }
                arr[i]=old;
            }
        }
        step++;
    }
    return -1;
}

复杂度

时间

O(N·L·4)

N=库里基因数，每个基因有 L=8 位、每位试 4 种字母去匹配库

空间

O(N)

队列和已访问集合最多装下库里全部基因

看不够？换成动画再走一遍

上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着最小基因变化的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。

看交互动画版 →更多图解题

面试官可能追问

为什么这题用 BFS 而不是 DFS？+

要的是「最少变化次数」=无权图最短路径。BFS 按层扩展，第一次到 end 即最短；DFS 找到的路径不保证最短，还得遍历所有路径再取最小，更慢。

如何枚举一个基因的所有合法邻居？+

能不能用双向 BFS 优化？+

可以。同时从 start 和 end 两端往中间扩，哪端队列小就扩哪端，两端相遇即得答案，能把搜索空间从近似 b^d 降到 2·b^(d/2)，对深度大的图更快。

想听吴师兄把这道题讲给你听？

了解年卡方案 →先去动画页看完整样板 →

把这道题真正拿下

看动画图解 →最小基因变化交互动画,逐步看清每一步怎么走

最小基因变化 图解题解

这道题到底在问什么

最优解：一步一步想明白

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

Python

C++

Java

复杂度

看不够？换成动画再走一遍

面试官可能追问

想听吴师兄把这道题讲给你听？

最小基因变化 图解题解

这道题到底在问什么

最优解：一步一步想明白

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

Python

C++

Java

复杂度

看不够？换成动画再走一遍

面试官可能追问

想听吴师兄把这道题讲给你听？

最小基因变化图解题解

最小基因变化图解题解