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

知识点

BFS 最短路

思路

每一步的代价为1，可以用BFS求最短路。每次搜索尝试把每个字母换成“ACGT”中的一个，如果在备选中则可以加入队列。

具体细节和上一题完全一致。

AC Code（C++）

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param start string字符串 
     * @param end string字符串 
     * @param bank string字符串vector 
     * @return int整型
     */
    using psi = pair<string, int>;
    const string table = "ACGT";
    int minMutation(string start, string end, vector<string>& bank) {
        if (start == end) return 0;
        // bfs最短路
        unordered_set<string> S(bank.begin(), bank.end());
        queue<psi> q;
        q.emplace(start, 0);
        S.erase(start);
        while (!q.empty()) {
            auto [s, step] = q.front();
            q.pop();
            for (int i = 0; i < s.size(); i ++) {
                for (char c : table) {
                    if (s[i] == c) continue;
                    auto t = s[i];
                    s[i] = c;
                    if (S.count(s)) {
                        if (s == end) return step + 1;
                        S.erase(s);
                        q.emplace(s, step + 1);
                    }
                    s[i] = t;
                }
            }
        }
        return -1;
    }
};