C++ bidirectional BFS. Straightforward level tracking.


  • 0
    S

    Traditional BFS search from both ends. set1 is used to keep current letter nodes for forward search and set2 is for - search from the end. 'adjacent' set is used to build a set for the next search level. Marked[] entries keep state of dictionary nodes: 0 - unmarked, 1 - marked by forward search, 2 - marked by backward search. Direction of the search switched to opposite when current search 'discovered' more nodes then the opposite one. Swapping of sets is O(1).

    In my opinion using vectors over queues simplifies design.

    Space: O(N) - approximately 3 integers for each string in dictionary plush hash sets overhead. Each hash set (unordered_map) reserves N bucket slots upfront to enjoy perfect hash - I did not play with other values.

    class Solution {
    public:
        bool words_are_close(string& w1, string& w2) {
            int diff_count = 0;
            for (int i = 0; i < (int)w1.size(); i++) {
                if (w1[i] != w2[i]) {
                    if (++diff_count > 1)
                        return false;
                }
            }
            return diff_count == 1;
        }
        int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
            int                     n = (int)wordList.size();
            vector<unsigned char>   marked(n + 1, 0);
            unordered_set<int>      set1(n);
            unordered_set<int>      adjacent(n);
            unordered_set<int>      set2(n);
            
            auto it = find(wordList.begin(), wordList.end(), endWord);
            if (it == wordList.end())
                return 0;
            set2.insert(it - wordList.begin());
            marked[it - wordList.begin()] = 2;      //direction from endWord
    
            it = find(wordList.begin(), wordList.end(), beginWord);
            int ibegin_word = it - wordList.begin();
            set1.insert(ibegin_word);    
            marked[ibegin_word] = 1;                //direction from beginWord
            
            unsigned char opp_dir = 2;
            for (int level = 0; !set1.empty() && !set2.empty(); level++) {
                if (set2.size() < set1.size()) {
                    swap(set1, set2); 
                    opp_dir ^= 3;                   //flip direction to opposite
                }
                for (int iword : set1) {
                    string& word = (iword == ibegin_word) ? beginWord : wordList[iword];
                    for (int i = 0; i < n; i++) { 
                        if (
                            (marked[i] == 0 || (marked[i] == opp_dir && set2.find(i) != set2.end()))
                            && 
                            words_are_close(word, wordList[i])
                        ) {
                            if (marked[i] == opp_dir)
                                return level + 2;
                            
                            adjacent.insert(i);
                            marked[i] = opp_dir ^ 3;
                        }
                    }
                }
                set1.clear();
                swap(set1, adjacent);
            }    
            return 0;
        }
    };
    

Log in to reply
 

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