c++ bi-directional BFS


  • 0
    T
    class Solution {
    public:
        vector<vector<string>> findLadders(string beginWord, string endWord, vector<string>& wordList) {
            unordered_map<string, vector<string>> graph;
            unordered_set<string> dict(wordList.begin(), wordList.end());
            unordered_set<string> fwd{beginWord}, bwd{endWord};
    
            vector<vector<string>> rst;
            vector<string> path{beginWord};
            if (dict.find(endWord) == dict.end() || !find(graph, fwd, bwd, dict, false)) 
                return rst;
    
            recover_path(rst, path, beginWord, endWord, graph);
            return rst;
        }
        
        void recover_path(vector<vector<string>> &rst, vector<string> &path, 
            string &from, string &to, unordered_map<string, vector<string>> &graph) {
            if (from == to) {
                rst.push_back(path);
                return;
            }
            for (string &s:graph[from]) {
                path.push_back(s);
                recover_path(rst, path, s, to, graph);
                path.pop_back();
            }
        }
    
        bool find(unordered_map<string, vector<string>>&graph, unordered_set<string> &fwd, 
            unordered_set<string> &bwd, unordered_set<string> &dict, bool reverse) {
            if (fwd.size() > bwd.size() || fwd.empty()) {
                return fwd.empty() ? false:find(graph, bwd, fwd, dict, !reverse);
            }
            for (auto &s:fwd) dict.erase(s);
            for (auto &s:bwd) dict.erase(s);
    
            bool found = false;
            unordered_set<string> next;
            for (auto &word:fwd) {
                string tword = word;
                for (char &ch:tword) {
                    char tch = ch;
                    for (char c = 'a'; c <= 'z'; ++c) {
                        if (c == ch) continue;
                        ch = c;
                        if (bwd.find(tword) != bwd.end()) {
                            !reverse ? graph[word].push_back(tword) : graph[tword].push_back(word);
                            found = true; // in case of skipping other solutions
                        } else if (dict.find(tword) != dict.end() && !found) {
                            next.insert(tword);
                            !reverse ? graph[word].push_back(tword) : graph[tword].push_back(word);
                        }
                        ch = tch;
                    }
                }
            }
            return found || find(graph, next, bwd, dict, reverse);
        }
    };
    

Log in to reply
 

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