C++ dirty bidirectional BFS + DFS, 42ms


  • 1
    C

    Here are my understandings why this problem is considered difficult:

    1. BFS early termination. As long as target word is found(for one directional bfs), Or left/right layer intersect(bidirectional BFS), BFS should be terminated.
      Solution: adding a found flag in global context, if the condition above is met, then set the flag. The flag should be checked at the entry of BFS process each time.
    2. For each BFS layer, The next layer should be calculated without introducing loops to the graph.
      Solution: introducing one or two hashmaps, which indicate if current word has been visited.
    3. For each word, its neighbors should be calculated, and no duplicate words should exist in the same neighbor collection. However, within the same layer, each word's state calculation should not interfere any other word.
      Solution: for each word, maintain a hashmap for its neighbors. After all its neighbors are calculated, add them to the next layer's hashmap. When all the words' neighbors are populated, move them to the current layer and add them to the visited set.
    class Solution {
    public:
        vector<vector<string>> findLadders(string beginWord, string endWord, vector<string>& wordList) {
            unordered_map<string, unordered_set<string>> graph;
            unordered_set<string> curLeft, nextLeft, leftVisited;
            unordered_set<string> curRight, nextRight, rightVisited;
            unordered_set<string> dict(wordList.begin(), wordList.end());
            vector<vector<string>> res;
            if (dict.count(endWord) == 0)
                return res;
            dict.insert(beginWord);
            bool found = false;
            leftVisited.insert(beginWord);
            rightVisited.insert(endWord);
            curLeft.insert(beginWord);
            curRight.insert(endWord);
            while (not found && not curLeft.empty() && not curRight.empty()) {
                if (curLeft.size() <= curRight.size()) {
                    for (string word: curLeft) {
                        string tmp = word;
                        unordered_set<string> nextLayer;
                        for (int i = 0; i < word.size(); ++i) {
                            char c = word[i];
                            for (char cc = 'a'; cc <= 'z'; ++cc) {
                                if (c == cc)
                                    continue;
                                word[i] = cc;
                                if (dict.count(word) && leftVisited.count(word) == 0 && graph[word].count(tmp) == 0) {
                                    nextLayer.insert(word);
                                    graph[word].insert(tmp);
                                }
                            }
                            word[i] = c;
                        }
                        for (string s: nextLayer) {
                            nextLeft.insert(s);
                            if (curRight.count(s))
                                found = true;
                        }
                    }
                    curLeft.swap(nextLeft);
                    for (auto s: curLeft)
                        leftVisited.insert(s);
                    nextLeft.clear();
                }
                else {
                    for (string word: curRight) {
                        string tmp = word;
                        unordered_set<string> nextLayer;
                        for (int i = 0; i < word.size(); ++i) {
                            char c = word[i];
                            for (char cc = 'a'; cc <= 'z'; ++cc) {
                                if (c == cc)
                                    continue;
                                word[i] = cc;
                                if (dict.count(word) && rightVisited.count(word) == 0 && graph[tmp].count(word) == 0) {
                                    nextLayer.insert(word);
                                    graph[tmp].insert(word);
                                }
                            }
                            word[i] = c;
                        }
                        for (string s: nextLayer) {
                            nextRight.insert(s);
                            if (curLeft.count(s))
                                found = true;
                        }
                    }
                    curRight.swap(nextRight);
                    for (auto s: curRight)
                        rightVisited.insert(s);
                    nextRight.clear();
                }
            }
            vector<string> buf;
            helper(res, buf, graph, endWord, beginWord);
            return res;
        }
        void helper(vector<vector<string>>& res, vector<string>& buf, unordered_map<string, unordered_set<string>>& graph, string cur, const string& end) {
            if (cur == end) {
                vector<string> tmp = buf;
                tmp.push_back(end);
                reverse(tmp.begin(), tmp.end());
                res.push_back(tmp);
                return;
            }
            buf.push_back(cur);
            for (const auto& s: graph[cur]) {
                helper(res, buf, graph, s, end);
            }
            buf.pop_back();
        }
    };
    

Log in to reply
 

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