C++ BFS solution


  • 0
    G
    class Solution {
    public:
        int minMutation(string start, string end, vector<string>& bank) {
            if (start == end)
                return 0;
            
            unordered_map<string, bool> bankMap;
            for (size_t i = 0; i < bank.size(); ++i)
                bankMap[bank[i]] = true;
            
            return getMinMutation(start, end, bankMap);
        }
    
    private:
        int getMinMutation(string start, string end, unordered_map<string, bool>& bank) {
            unordered_map<string, int> mutations;
            queue<string> q;
            q.push(start);
            mutations[start] = 0;
            
            while (!q.empty()) {
                string crt = q.front();
                q.pop();
                
                if (crt == end)
                    return mutations[crt];
                
                for (size_t i = 0; i < crt.length(); ++i) {
                    if (crt[i] != end[i]) {
                        string potentialNextString = crt;
                        potentialNextString[i] = end[i];
                        if (bank.find(potentialNextString) != bank.end()) {
                            mutations[potentialNextString] = mutations[crt] + 1;
                            q.push(potentialNextString);
                        }
                    }
                }
            }
            
            return -1;
        }
    };
    

  • 0
    M

    Sorry,your code can't pass this testcase

    "AACCGGTT"
    "AAACGGTA"
    ["AACCGATT","AACCGATA","AAACGATA","AAACGGTA"]


Log in to reply
 

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