Easy C++ BFS, no helper method.


  • 0
    K

    Push a empty string for each level of BFS. When encounter an empty string, increment the counting variable. In addition, if the queue is not empty, push a new empty string.

    class Solution {
    public:
        int minMutation(string start, string end, vector<string>& bank) {
            if (start == end) return 0;
            unordered_set<string> bankset(bank.begin(), bank.end());
            unordered_set<string> as;
            queue<string> aq;
            char gene[] = {'A','C','T','G'};
            int step = 0;
            
            aq.push(start);
            as.insert(start);
            aq.push("");
            
            while (!aq.empty()) {
                string tmp = aq.front();
                aq.pop();
                if (tmp == "") {
                    if (!aq.empty()) aq.push("");
                    step++;
                }else{
                    if (tmp == end) return step;
                    for (int i = 0; i < tmp.length(); i++) {
                        char t = tmp[i];
                        for (char ch : gene) {
                            tmp[i] = ch;
                            if (as.find(tmp) == as.end() && bankset.find(tmp) != bankset.end()){
                                aq.push(tmp);
                                as.insert(tmp);
                            }
                        }
                        tmp[i] = t;
                    }
                }
              
            }
            return -1;
        }
    };
    

Log in to reply
 

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