Minimum Genetic Mutation

433. 最小基因变化

分析

数据准备
- 将基因库 bank 存入一个哈希集合 gene 中，方便快速判断某个基因序列是否有效
- 用哈希表 hash 记录每个基因序列的访问状态及其变化次数
初始化 BFS
- 将起始基因序列 startGene 入队，设初始变化次数为 0
BFS 遍历
- 每次从队列中取出当前基因序列 s，对其进行逐位变换。
- 枚举 8 个字符中的每一位，尝试将其替换为 ‘A’、‘C’、‘G’ 或 ‘T’
- 对于每个生成的新基因序列 t，若它在基因库中且未被访问过
  - 将其加入队列，并记录变化次数 hash[t] = hash[s] + 1
  - 若 t == endGene，则直接返回变化次数
结束条件：
- 如果 BFS 遍历完队列仍未找到 endGene，则返回 -1

时间复杂度

每个基因序列有 8 个字符，每个字符有 4 种变换，最多产生 O(8 * 4 * n) 次尝试，其中 n 是基因库的大小
BFS 遍历每个基因序列一次，复杂度为 O(n)

总时间复杂度为 O(32n) ，即 O(n)

空间复杂度

哈希集合 gene 和 hash 占用 O(n) 空间
队列最多存储 O(n) 个基因序列

总空间复杂度为 O(n)

C++代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42


class Solution
{
public:
    int minMutation(string startGene, string endGene, vector<string>& bank)
    {
        // 基因库存入哈希集合
        std::unordered_set<std::string> gene;
        for (std::string& b : bank)
            gene.insert(b);

        // BFS 相关数据结构
        std::unordered_map<std::string, int> hash; // 记录访问状态及变化次数
        std::queue<std::string> q;
        hash[startGene] = 0; // 起始基因变化次数为 0
        q.push(startGene);

        char ge_ch[4] = {'A', 'C', 'G', 'T'}; // 可用字符
        while (!q.empty()) {
            std::string s = q.front();
            q.pop();

            // 对当前基因序列逐位尝试变换
            for (int i = 0; i < s.size(); ++i)
            {
                std::string t = s; // 新的基因序列
                for (char c : ge_ch)
                {
                    t[i] = c; // 修改第 i 位
                    // 若新序列有效且未访问过
                    if (gene.count(t) && hash.count(t) == 0)
                    {
                        hash[t] = hash[s] + 1; // 记录变化次数
                        if (t == endGene) // 找到目标序列
                            return hash[t];
                        q.push(t); // 入队继续搜索
                    }
                }
            }
        }
        return -1; // 无法到达目标序列
    }
};