Medium

题目描述

基因序列可以表示为一条由8个字符组成的字符串，从 ‘A’, ‘C’, ‘G’, ‘T’ 中选择。

假设我们要研究从基因字符串 startGene 到基因字符串 endGene 的变化过程，其中一次基因变化是指基因字符串中的一个字符发生了变化。

  • 例如，“AACCGGTT” –> “AACCGGTA” 即是一次基因变化。

另有一个基因库 bank 记录了所有有效的基因变化，只有基因库中的基因才是有效的基因字符串。

现在给定两个基因字符串 startGene 和 endGene，以及基因库 bank，请找出能够使 startGene 变化为 endGene 所需的最少变化次数。如果无法实现目标变化，返回 -1。

注意起始基因默认是有效的，因此它可能不包含在基因库中。

示例 1：

输入：startGene = "AACCGGTT", endGene = "AACCGGTA", bank = ["AACCGGTA"]
输出：1

示例 2：

输入：startGene = "AACCGGTT", endGene = "AAACGGTA", bank = ["AACCGGTA","AACCGCTA","AAACGGTA"]
输出：2

提示：

  • 0 <= bank.length <= 10
  • startGene.length == endGene.length == bank[i].length == 8
  • startGene, endGene, 和 bank[i] 仅由字符 [‘A’, ‘C’, ‘G’, ‘T’] 组成

解题思路

这是一个典型的最短路径问题，可以用 广度优先搜索（BFS） 来解决。

解题思路

基本思路： 将基因变化看作图中的路径搜索，每个基因字符串是一个节点，如果两个基因字符串只相差一个字符，则它们之间存在一条边。我们要找的是从起始基因到目标基因的最短路径。

具体步骤：

  1. 建立基因库集合： 为了快速查找基因是否有效，将 bank 转换为哈希集合
  2. BFS搜索： 使用队列进行广度优先搜索，从 startGene 开始
  3. 生成邻居节点： 对于当前基因，尝试改变每个位置的字符（A、C、G、T），如果变化后的基因在基因库中且未访问过，则加入队列
  4. 标记访问： 使用访问集合避免重复访问同一基因
  5. 返回结果： 当找到目标基因时返回步数，如果队列为空仍未找到则返回-1

为什么用BFS： BFS能保证第一次到达目标节点时使用的步数是最少的，这正是我们要求的最小变化次数。

时间优化： 由于基因长度固定为8，字符集大小为4，每个基因最多有24个邻居，加上基因库较小，整体复杂度很低。

代码实现

class Solution {
public:
    int minMutation(string startGene, string endGene, vector<string>& bank) {
        unordered_set<string> bankSet(bank.begin(), bank.end());
        if (bankSet.find(endGene) == bankSet.end()) {
            return -1;
        }
        
        queue<pair<string, int>> q;
        unordered_set<string> visited;
        q.push({startGene, 0});
        visited.insert(startGene);
        
        vector<char> genes = {'A', 'C', 'G', 'T'};
        
        while (!q.empty()) {
            auto [current, steps] = q.front();
            q.pop();
            
            if (current == endGene) {
                return steps;
            }
            
            for (int i = 0; i < 8; i++) {
                char originalChar = current[i];
                for (char gene : genes) {
                    if (gene == originalChar) continue;
                    
                    current[i] = gene;
                    if (bankSet.count(current) && !visited.count(current)) {
                        visited.insert(current);
                        q.push({current, steps + 1});
                    }
                }
                current[i] = originalChar;
            }
        }
        
        return -1;
    }
};

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}
        genes = ['A', 'C', 'G', 'T']
        
        while queue:
            current, steps = queue.popleft()
            
            if current == endGene:
                return steps
            
            for i in range(8):
                for gene in genes:
                    if gene == current[i]:
                        continue
                    
                    next_gene = current[:i] + gene + current[i+1:]
                    if next_gene in bank_set and next_gene not in visited:
                        visited.add(next_gene)
                        queue.append((next_gene, steps + 1))
        
        return -1

public class Solution {
    public int MinMutation(string startGene, string endGene, string[] bank) {
        var bankSet = new HashSet<string>(bank);
        if (!bankSet.Contains(endGene)) {
            return -1;
        }
        
        var queue = new Queue<(string gene, int steps)>();
        var visited = new HashSet<string>();
        queue.Enqueue((startGene, 0));
        visited.Add(startGene);
        
        char[] genes = {'A', 'C', 'G', 'T'};
        
        while (queue.Count > 0) {
            var (current, steps) = queue.Dequeue();
            
            if (current == endGene) {
                return steps;
            }
            
            for (int i = 0; i < 8; i++) {
                char originalChar = current[i];
                foreach (char gene in genes) {
                    if (gene == originalChar) continue;
                    
                    var nextGene = current.Substring(0, i) + gene + current.Substring(i + 1);
                    if (bankSet.Contains(nextGene) && !visited.Contains(nextGene)) {
                        visited.Add(nextGene);
                        queue.Enqueue((nextGene, steps + 1));
                    }
                }
            }
        }
        
        return -1;
    }
}

var minMutation = function(startGene, endGene, bank) {
    if (!bank.includes(endGene)) return -1;
    
    const queue = [[startGene, 0]];
    const visited = new Set([startGene]);
    const chars = ['A', 'C', 'G', 'T'];
    
    while (queue.length > 0) {
        const [current, mutations] = queue.shift();
        
        if (current === endGene) return mutations;
        
        for (let i = 0; i < 8; i++) {
            for (const char of chars) {
                if (char !== current[i]) {
                    const next = current.slice(0, i) + char + current.slice(i + 1);
                    if (bank.includes(next) && !visited.has(next)) {
                        visited.add(next);
                        queue.push([next, mutations + 1]);
                    }
                }
            }
        }
    }
    
    return -1;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(N × M × 4)N为基因库大小，M为基因长度(8)，4为字符集大小
空间复杂度O(N)存储基因库集合和访问记录

相关题目