Easy C++ BFS solution


  • 0
    P
    class Solution {
    public:
        int minMutation(string start, string end, vector<string>& bank) {
            if (start == end) { // missing test case?
                return 0;
            }
    
            queue<string> q;
            int size = bank.size();
            q.push(start);
            q.push("");
            
            int cnt = 0;
            while (!q.empty()) {
                string s = q.front();
                q.pop();
                
                if (s.empty()) {
                    if (q.empty()) {
                        break;
                    }
                    q.push("");
                    ++cnt;
                    continue;
                }
                
                for (int i = 0; i < size; ) {
                    string &sb = bank[i];
                    if (!isMutation(s, sb)) {
                        ++i;
                        continue;
                    }
                    if (sb == end) {
                        return cnt + 1;
                    }
                    q.push(sb);
                    if (i != size - 1) {
                        bank[i] = bank[size - 1];
                    }
                    --size;
                }
                
            }
            
            return -1;
        }
        
        bool isMutation(string &a, string &b) {
            int l = a.length();
            if (l != b.length()) {
                return false;
            }
            int cnt = 0;
            for (int i = 0; i < l; ++i) {
                if (a[i] == b[i]) {
                    continue;
                }
                if (++cnt > 1) {
                    return false;
                }
            }
            return cnt == 1;
        }
    };
    

Log in to reply
 

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