C++ two end BFS solution, exactly same as 127.Word Ladder


  • 5
    T

    If the length of gene is limited, maybe we can consider to encode ATGC with 2 bits

    class Solution {
    public:
        int minMutation(string start, string end, vector<string>& bank) {
            unordered_set<string> dict(bank.begin(), bank.end());
            if (!dict.count(end)) return -1;
            unordered_set<string> bset, eset, *set1, *set2;
            bset.insert(start), eset.insert(end);
            int step = 0, n = start.size();
            while (!bset.empty() and !eset.empty()) {
                if (bset.size() <= eset.size())
                    set1 = &bset, set2 = &eset;
                else set2 = &bset, set1 = &eset;
                unordered_set<string> tmp;
                step ++;
                for (auto itr = set1->begin(); itr != set1->end(); ++itr) {
                    for (int i = 0; i < n; ++i) {
                        string dna = *itr;
                        for (auto g : string("ATGC")) {
                            dna[i] = g;
                            if (set2->count(dna)) return step;
                            if (dict.count(dna)) {
                                tmp.insert(dna);
                                dict.erase(dna);
                            }
                        }
                    }
                }
                *set1 = tmp;
            }
            return -1;
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.