Steward

分享是一種喜悅、更是一種幸福

程式語言 - LeetCode - C++ - 433. Minimum Genetic Mutation

---

題目：


解答：

class Solution {
public:
    int minMutation(string startGene, string endGene, vector<string>& bank) {
        unordered_set<string> valid(bank.begin(), bank.end());

        if (!valid.count(endGene)) {
            return -1;
        }

        queue<pair<string, int>> q;
        q.push({startGene, 0});

        unordered_set<string> visited;
        visited.insert(startGene);

        vector<char> gene = {'A', 'C', 'G', 'T'};

        while (!q.empty()) {
            auto [cur, step] = q.front();
            q.pop();

            if (cur == endGene) {
                return step;
            }

            for (int i = 0; i < cur.size(); ++i) {
                string next = cur;

                for (char g : gene) {
                    if (next[i] == g) {
                        continue;
                    }

                    next[i] = g;
                    if (valid.count(next) && !visited.count(next)) {
                        visited.insert(next);
                        q.push({next, step + 1});
                    }
                }
            }
        }

        return -1;
    }
};