0433. 最小基因变化【中等】

• 1. 📝 题目描述
• 2. 🎯 s.1 - BFS

1. 📝 题目描述

• leetcode

基因序列可以表示为一条由 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'] 组成

2. 🎯 s.1 - BFS

c

int minMutation(char* startGene, char* endGene, char** bank, int bankSize) {
    bool inBank[bankSize];
    memset(inBank, true, sizeof(inBank));
    // BFS
    char queue[bankSize + 1][9];
    int steps[bankSize + 1];
    int front = 0, rear = 0;
    strcpy(queue[rear], startGene); steps[rear++] = 0;
    bool visited[bankSize];
    memset(visited, false, sizeof(visited));
    while (front < rear) {
        char* gene = queue[front];
        int step = steps[front++];
        for (int i = 0; i < bankSize; i++) {
            if (visited[i]) continue;
            int diff = 0;
            for (int j = 0; j < 8; j++) if (gene[j] != bank[i][j]) diff++;
            if (diff == 1) {
                if (strcmp(bank[i], endGene) == 0) return step + 1;
                visited[i] = true;
                strcpy(queue[rear], bank[i]); steps[rear++] = step + 1;
            }
        }
    }
    return -1;
}

js

/**
 * @param {string} startGene
 * @param {string} endGene
 * @param {string[]} bank
 * @return {number}
 */
var minMutation = function (startGene, endGene, bank) {
  const bankSet = new Set(bank)
  if (!bankSet.has(endGene)) return -1
  const queue = [[startGene, 0]]
  const visited = new Set([startGene])
  while (queue.length) {
    const [gene, step] = queue.shift()
    for (let i = 0; i < 8; i++) {
      for (const ch of 'ACGT') {
        const next = gene.slice(0, i) + ch + gene.slice(i + 1)
        if (next === endGene) return step + 1
        if (bankSet.has(next) && !visited.has(next)) {
          visited.add(next)
          queue.push([next, step + 1])
        }
      }
    }
  }
  return -1
}

py

class Solution:
    def minMutation(self, startGene: str, endGene: str, bank: List[str]) -> int:
        bank_set = set(bank)
        if endGene not in bank_set:
            return -1
        queue = deque([(startGene, 0)])
        visited = {startGene}
        while queue:
            gene, step = queue.popleft()
            for i in range(8):
                for ch in 'ACGT':
                    nxt = gene[:i] + ch + gene[i+1:]
                    if nxt == endGene:
                        return step + 1
                    if nxt in bank_set and nxt not in visited:
                        visited.add(nxt)
                        queue.append((nxt, step + 1))
        return -1

• 时间复杂度：$O(C\times n\times |\mathrm{\Sigma }|)$，其中 $C=8$ 是基因长度，$|\mathrm{\Sigma }|=4$
• 空间复杂度：$O(n)$

算法思路：

• BFS 求最短路径，每次变化一个字符
• 只有基因库中的序列才是合法状态