C++ Super Concise and Fast 2 Way BFS


  • 0
    Z
    class Solution {
    public:
        vector<vector<string>> findLadders(string beginWord, string endWord, vector<string>& wordList) {
            unordered_set<string> wordDict(wordList.begin(), wordList.end());
            if (wordDict.find(endWord) == wordDict.end()) return {};
            
            bool found = false, nothing = false;
            int cur = 0, next = 1, len = wordList[0].length();
            vector<vector<string>> ret;
            unordered_set<string> myDict[2];
            unordered_map<string, vector<string>> backtrack;    
            wordDict.erase(beginWord);
            wordDict.erase(endWord);
            myDict[cur].insert(beginWord);
            myDict[next].insert(endWord);
            
            while (true) {
                if (nothing || found) break;
                nothing = true;
                unordered_set<string> prop;
                for (auto &u : myDict[cur]) {
                    for (int i = 0; i < len; ++i) {
                        string str = u;
                        for (str[i] = 'a'; str[i] <= 'z'; ++str[i]) {
                            if (myDict[next].find(str) != myDict[next].end()) {
                                found = true;
                                cur ? backtrack[str].push_back(u) : backtrack[u].push_back(str);
                            } else if (!found) {
                                if (wordDict.find(str) == wordDict.end()) continue;
                                nothing = false;
                                cur ? backtrack[str].push_back(u) : backtrack[u].push_back(str);
                                prop.insert(str);
                            }
                        }
                    }
                }
                for (string s : prop) wordDict.erase(s);
                myDict[cur].swap(prop);
                swap(cur, next);
            }       
            vector<string> tmp = {beginWord};
            backward(backtrack, tmp, beginWord, endWord, ret);        
            return ret;
        }
    
    private:
        void backward(unordered_map<string, vector<string>> &backtrack, vector<string> &tmp, string bw, string ew, vector<vector<string>> &ret) {
            if (backtrack[bw].empty()) {
                if (bw == ew) ret.push_back(tmp);
                return;
            }
            for (string s : backtrack[bw]) {
                tmp.push_back(s);
                backward(backtrack, tmp, s, ew, ret);
                tmp.pop_back();
            }
        }
    };
    

Log in to reply
 

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