433.最小基因变化

链接：433.最小基因变化
难度：Medium
标签：广度优先搜索、哈希表、字符串
简介：给你两个基因序列 start 和 end ，以及一个基因库 bank ，请你找出并返回能够使  start 变化为 end 所需的最少变化次数。如果无法完成此基因变化，返回 -1 。

题解 1 - cpp

• 编辑时间：2022-05-07
• 内存消耗：6.4MB
• 编程语言：cpp
• 解法介绍：bfs。

class Solution {
public:
    int minMutation(string start, string end, vector<string>& bank) {
        unordered_set<string> s;
        for (auto &v : bank) s.insert(v);
        queue<string> q;
        q.push(start);
        int level = 0, size = 1;
        while (q.size()) {
            string cur = q.front(); q.pop();
            if (cur == end) return level;
            for (auto &s : next(s, cur)) q.push(s);
            if (--size == 0) { size = q.size(); level++; }
        }
        return -1;
    }
    char list[4] = {'A', 'C', 'G', 'T'};
    vector<string> next(unordered_set<string> &s, string &str) {
        vector<string> ans;
        for (int i = 0; i < 8; i++) {
            for (int j = 0; j < 4; j++) {
                if (str[i] == list[j]) continue;
                string next = str;
                next[i] = list[j];
                if (s.count(next)) {
                    ans.emplace_back(next);
                    s.erase(next);
                }
            }
        }
        return ans;
    }
};