LeetCode 433. 最小基因变化

题目描述
给定两个字符串 start 和 end，以及一个字符串数组 bank，bank 中存放了有效的基因序列列表。你的目标是进行基因变化，从 start 变化到 end。每次变化只能改变一个字符，并且变化后的基因序列必须存在于 bank 中。你需要找出从 start 变化到 end 所需的最少变化次数。如果无法完成变化，返回 -1。

示例：

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

解释：只需将 start 的最后一个字符 'T' 改为 'A'，得到 end，且 end 在 bank 中，所以变化 1 次。

注意：

1. start 和 end 长度相同，且长度范围为 [1, 8]。
2. bank 中的字符串长度与 start 相同，且不会重复。
3. 所有字符串仅由字符 'A', 'C', 'G', 'T' 组成。

解题过程循序渐进讲解

第一步：理解问题核心
这个问题本质上是一个最短路径搜索问题。

• 将每个基因序列视为一个状态节点。
• 如果两个基因序列之间只有一个字符不同，则它们之间有一条无向边（可以互相变化）。
• 从起始状态 start 出发，通过若干次变化（即走过若干条边），到达目标状态 end。
• 要求出最短路径长度（最少变化次数）。
• 注意：变化后的状态必须在 bank 中（bank 是合法状态的集合），但 start 可以不在 bank 中。
• 如果 end 不在 bank 中，则直接返回 -1，因为不可能合法变化到 end。

第二步：明确搜索思路
因为要找最短路径，自然想到用广度优先搜索（BFS）。BFS 从 start 出发，逐层探索，第一次遇到 end 时的层数就是最少变化次数。
为什么 BFS 合适？

• 每次变化代价为 1（即边权相同），BFS 可以保证首次到达时的路径最短。
• 状态空间不大：每个位置可以是 4 种字符，长度 ≤8，但实际合法状态数不超过 bank.size() ≤ 10，所以 BFS 很快。

第三步：BFS 的具体步骤

1. 预处理：将 bank 存入一个哈希集合，以便 O(1) 判断一个状态是否合法。
2. 检查 end 是否在 bank 中，如果不在，直接返回 -1。
3. 初始化队列 queue，用于 BFS，队列元素是 (当前基因序列, 当前变化次数)。
4. 初始化一个 visited 集合，记录已访问过的状态，避免重复访问。
5. 将 (start, 0) 入队，并标记 start 为已访问。
6. 当队列不为空时，循环：
   • 弹出队首元素 (current, steps)。
   • 如果 current == end，返回 steps。
   • 否则，生成 current 的所有可能的下一个状态：对 current 的每个位置，尝试替换成另外 3 个字符（'A','C','G','T' 中不同于当前字符的），得到新序列 next。
   • 如果 next 在 bank 中且未被访问过，将其标记为已访问，并将 (next, steps+1) 入队。
7. 如果 BFS 结束仍未找到 end，返回 -1。

第四步：举例说明 BFS 过程
以示例为例：

start = "AACCGGTT"
end   = "AACCGGTA"
bank = ["AACCGGTA"]

1. 初始化：end 在 bank 中，合法。visited={}，队列初始为 [("AACCGGTT", 0)]。
2. 弹出 ("AACCGGTT", 0)，不等于 end。
3. 生成它的所有单字符变化：
   • 改变位置 7（最后一个字符）：'T' -> 'A' 得到 "AACCGGTA"，这个序列在 bank 中，且未访问过，将其入队 ("AACCGGTA", 1)，标记已访问。
4. 弹出 ("AACCGGTA", 1)，发现等于 end，返回 1。

第五步：边界情况处理

1. 如果 start == end，那么不需要变化，返回 0。
2. 如果 end 不在 bank 中，直接返回 -1，因为不可能合法到达。
3. 如果 bank 为空，且 start != end，返回 -1。
4. 在生成下一个状态时，注意排除与当前字符相同的情况，减少无谓判断。

第六步：复杂度分析

• 设基因序列长度为 L，bank 中基因个数为 N。
• 每个状态在 BFS 中最多被访问一次，状态数为 O(N)（包括 start）。
• 每个状态生成下一个状态时，需要遍历 L 个位置，每个位置尝试 3 个不同字符，所以每个状态最多生成 3L 个新序列。
• 检查新序列是否在 bank 中（哈希集合 O(1)），并检查是否访问过（哈希集合 O(1)）。
• 总时间复杂度 O(N * L)，这里 L ≤ 8，N ≤ 10，所以非常快。
• 空间复杂度 O(N)，用于存储 bank 集合和 visited 集合。

第七步：实现细节（伪代码）

function minMutation(start, end, bank):
    bankSet = set(bank)
    if end not in bankSet:
        return -1
    queue = deque()
    queue.append((start, 0))
    visited = set()
    visited.add(start)
    charSet = ['A', 'C', 'G', 'T']
    
    while queue:
        current, steps = queue.popleft()
        if current == end:
            return steps
        for i in range(len(current)):
            for ch in charSet:
                if ch == current[i]:
                    continue
                nextGene = current[:i] + ch + current[i+1:]
                if nextGene in bankSet and nextGene not in visited:
                    visited.add(nextGene)
                    queue.append((nextGene, steps+1))
    return -1

第八步：进一步思考
这个问题也可以用双向 BFS 优化，但状态空间很小，普通 BFS 已足够。另外，如果 bank 很大，也可以预先建立邻接表，但本题不需要。