What is the main pattern used in Minimum Genetic Mutation?

The problem combines a hash table for fast gene validation and BFS to explore minimal mutation paths efficiently.

How do I handle genes not in the bank?

Ignore any mutation not present in the hash table to ensure only valid gene sequences are considered.

Can mutations revert a previously changed character?

No, previously visited genes should be tracked to prevent cycles; each mutation sequence must be unique.

What determines the BFS step count?

Each BFS level corresponds to one mutation step; reaching endGene at level k means k mutations.

What if startGene equals endGene?

Return 0 mutations immediately since no changes are needed.

#433

Medium

auto_awesome图·搜索

LeetCode 题解工作台

最小基因变化

基因序列可以表示为一条由 8 个字符组成的字符串，其中每个字符都是 'A' 、 'C' 、 'G' 和 'T' 之一。假设我们需要调查从基因序列 start 变为 end 所发生的基因变化。一次基因变化就意味着这个基因序列中的一个字符发生了变化。例如， "AACCGGTT" --> "AACCG…

哈希表字符串广度优先搜索

题目描述

基因序列可以表示为一条由 8 个字符组成的字符串，其中每个字符都是 'A'、'C'、'G' 和 'T' 之一。

假设我们需要调查从基因序列 start 变为 end 所发生的基因变化。一次基因变化就意味着这个基因序列中的一个字符发生了变化。

例如，"AACCGGTT" --> "AACCGGTA" 就是一次基因变化。

另有一个基因库 bank 记录了所有有效的基因变化，只有基因库中的基因才是有效的基因序列。（变化后的基因必须位于基因库 bank 中）

给你两个基因序列 start 和 end ，以及一个基因库 bank ，请你找出并返回能够使 start 变化为 end 所需的最少变化次数。如果无法完成此基因变化，返回 -1 。

注意：起始基因序列 start 默认是有效的，但是它并不一定会出现在基因库中。

示例 1：

输入：start = "AACCGGTT", end = "AACCGGTA", bank = ["AACCGGTA"]
输出：1

示例 2：

输入：start = "AACCGGTT", end = "AAACGGTA", bank = ["AACCGGTA","AACCGCTA","AAACGGTA"]
输出：2

示例 3：

输入：start = "AAAAACCC", end = "AACCCCCC", bank = ["AAAACCCC","AAACCCCC","AACCCCCC"]
输出：3

提示：

start.length == 8
end.length == 8
0 <= bank.length <= 10
bank[i].length == 8
start、end 和 bank[i] 仅由字符 ['A', 'C', 'G', 'T'] 组成

lightbulb

解题思路

方法一：BFS

我们定义一个队列 q，用于存储当前基因序列以及变化的次数，定义一个集合 vis，用于存储已经访问过的基因序列。初始时，将起始基因序列 start 加入队列 q，并将其加入集合 vis。

然后，我们不断从队列 q 中取出一个基因序列，如果该基因序列等于目标基因序列，则返回当前的变化次数。否则，我们遍历基因库 bank，计算当前基因序列与基因库中的基因序列的差异值，如果差异值为 $1$ ，且基因库中的基因序列没有被访问过，则将其加入队列 q，并将其加入集合 vis。

如果队列 q 为空，说明无法完成基因变化，返回 $-1$ 。

时间复杂度 $O(C \times n \times m)$ ，空间复杂度 $O(n \times m)$ 。其中 $n$ 和 $m$ 分别表示基因序列的长度和基因库的长度，而 $C$ 表示基因序列的字符集大小，本题中 $C = 4$ 。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

class Solution:
    def minMutation(self, startGene: str, endGene: str, bank: List[str]) -> int:
        q = deque([(startGene, 0)])
        vis = {startGene}
        while q:
            gene, depth = q.popleft()
            if gene == endGene:
                return depth
            for nxt in bank:
                diff = sum(a != b for a, b in zip(gene, nxt))
                if diff == 1 and nxt not in vis:
                    q.append((nxt, depth + 1))
                    vis.add(nxt)
        return -1

speed

复杂度分析

指标	值
时间	complexity is O(8 * 4^8) in the worst case due to generating all one-character mutations, but limited by bank size and BFS pruning. Space complexity is O(bank.length + queue size) for hash table and BFS queue.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Expect BFS usage due to minimal step requirement.
question_mark
Hash table for fast gene validation is crucial.
question_mark
Consider edge cases where endGene is not reachable from startGene.

warning

常见陷阱

外企场景

error
Mutating genes not present in the bank leading to invalid paths.
error
Failing to mark visited genes, causing cycles.
error
Counting steps incorrectly by not tracking BFS levels.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Allow multiple simultaneous mutations per step, requiring a modified BFS.
arrow_right_alt
Genes of variable length, requiring dynamic mutation generation.
arrow_right_alt
Large bank sizes, emphasizing memory-efficient hash table or pruning strategies.

help

常见问题

外企场景

继续练习

#721 账户合并 #127 单词接龙 #126 单词接龙 II