题解 | #基因变异最小次数#

考察的知识点：哈希、双向广度优先搜索；

解答方法分析：

1. 创建两个队列，分别存放起始基因序列和目标基因序列，以及两个哈希集合，分别存放起始基因序列访问过的序列和目标基因序列访问过的序列。
2. 初始化变化次数为0。
3. 进入循环，直到两个队列都为空。
4. 在每次循环中，分别从起始基因队列和目标基因队列中取出一个基因序列。
5. 对于起始基因序列，遍历该序列的每一个字符，将其替换为’A’、‘C’、'G’和’T’中的每一个，并判断替换后的基因是否有效且未被访问过。如果满足条件，则将该基因序列加入起始基因队列，并将其标记为已访问。
6. 对于目标基因序列，遍历该序列的每一个字符，将其替换为’A’、‘C’、'G’和’T’中的每一个，并判断替换后的基因是否有效且未被访问过。如果满足条件，则将该基因序列加入目标基因队列，并将其标记为已访问。
7. 在每次循环中，判断起始基因队列和目标基因队列中是否存在相同的基因序列。如果存在，则说明已经找到了最短变化路径，可以返回当前变化次数。
8. 如果循环结束，说明无法完成基因变化，返回-1。

所用编程语言：C++；

完整编程代码：↓

class Solution {
  public:
    int minMutation(string start, string end, vector<string>& bank) {
        unordered_set<string> geneBank(bank.begin(), bank.end());
        if (geneBank.find(end) == geneBank.end()) {
            return -1;
        }
        queue<string> q;
        q.push(start);
        unordered_set<string> visited;
        visited.insert(start);
        int level = 0;
        while (!q.empty()) {
            int size = q.size();
            for (int i = 0; i < size; i++) {
                string cur = q.front();
                q.pop();
                if (cur == end) {
                    return level;
                }
                for (int j = 0; j < cur.size(); j++) {
                    char original = cur[j];
                    for (char c : {
                                'A', 'C', 'G', 'T'
                            }) {
                        cur[j] = c;
                        if (geneBank.count(cur) && visited.count(cur) == 0) {
                            q.push(cur);
                            visited.insert(cur);
                        }
                    }
                    cur[j] = original;
                }
            }
            level++;
        }
        return -1;
    }
};