DFS with comments and check for only valid descendants


  • 0
    V
    int minMutation(string s, string e, vector<string>& bank) {
            int i, n = s.length(), level = 0;
            //bank.push_back(e);
            vector<set<char>> db(n);
            
            unordered_set<string> bs;
            for (auto x : bank) {
                bs.insert(x);
                for (i = 0; i < n; i++)
                    db[i].insert(x[i]);
            }
            queue<string> q;
            q.push(s);
            while (!q.empty()) {
                int cnt = q.size();
                while (cnt-- > 0) { // process the current level
                    string curr = q.front();
                    if (curr == e)
                        return level;
                    q.pop();
                    for (i = 0; i < n; i++) { // all positions of curr
                        for (auto c : db[i]) { // all possible chars at this pos
                            if (curr[i] == c) // can't mutate to same char
                                continue;
                            char old = curr[i];
                            curr[i] = c;
                            if (bs.find(curr) != bs.end()) {
                                bs.erase(curr);
                                q.push(curr);
                            }
                            curr[i] = old; // restore curr
                        }
                    }
                }
                level++;
            }
            return -1;
        }
    

Log in to reply
 

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