My C++ bi-directional BFS solution (O(N) time, O(N) space), 64ms


  • 10
    D

    The basic idea is to do BFS to search the shortest path. The only trick is to speed up the search, we do bi-directional search, in the sense that we may expand the current path to the next level either from the beginWord side or the endWord side, depending on which side has less nodes to be expanded. To implement the BFS, we need the following data structure

    1. unusedWords is an unordered_set that includes all the words in the dictionary that we haven't visited.
    2. activeWords[startSet] is an unordered_set that includes all the nodes we are going to expand with BFS.
    3. activeWords[endSet] is an unordered_set that includes all the ending nodes from the other side (or direction). If a BFS expanded path (from activeWords[startSet]) reaches one of the words in the endSet, then it means we find a shortest path.
    4. activeWords[nextSet] is an unordered set that saves the ending nodes of all the BFS expanded paths
      (from activeWords[startSet]).
    5. For each BFS step, we will dynamically decide at which direction we should expand. We always do BFS on the set that has less nodes. This will reduce the search complexity. So we may swap startSet and endSet.

    To do BFS, we go through each word in the startSet, check all possible word it can generate by changing a char, if the new word is in the endSet, then we find a shortest path and just return the current depth. Otherwise, we check if the new word is unuseded (i.e. in unusedWords), if yes, add the new word to nextSet and remove it from unusedWords. If it is visited before, just skip it.

    class Solution {
    public:
        int ladderLength(string beginWord, string endWord, unordered_set<string>& wordDict) {
            
            int srcLen = beginWord.size(), destLen = endWord.size(), dictSize = wordDict.size();
            if((srcLen != destLen) || !srcLen || !dictSize) return 0; // abnormal cases, return 0; // abnormal cases, just return 0
            
            unordered_set<string> unusedWords = wordDict; // words that never visited before
            unordered_set<string> activeWords[3];
            int startSet = 0, endSet = 1, nextSet = 2, curDepth = 2, i;
            char tempC, j;
             
            activeWords[startSet].insert(beginWord);
            activeWords[endSet].insert(endWord);
            unusedWords.erase(beginWord);
            unusedWords.erase(endWord);
    
            while(!activeWords[startSet].empty()) 
            { // do BFS on startSet
                for(auto it : activeWords[startSet])
                {
                    for(i = 0 ; i<srcLen; ++i)
                    {
                        for( tempC = it[i], j='a'; j<='z'; ++j)
                        {
                            if(tempC == j) continue;
                            it[i] = j;  
                            if(activeWords[endSet].count(it)>0)
                                return curDepth ;// if the new word is in the endSet, then we find a path
                            if(unusedWords.count(it))
                            { // otherwise, if it is a new word that has never been visited
                                activeWords[nextSet].insert(it);
                                unusedWords.erase(it); 
                            }
                        }// FOR j
                        it[i] = tempC;
                    } // FOR i
                } //FOR it
                ++curDepth;
                swap(startSet, nextSet); // swap the startSet and the nextSet
                if(activeWords[startSet].size() > activeWords[endSet].size()) swap(startSet, endSet); // if needed, switch the search direction 
                activeWords[nextSet].clear();
            }
            return 0;
        }
    };

  • 0
    C

    "To implement the DFS"? I think should be BFS.


  • 0
    D

    Typo corrected, thanks for pointing it out to me,


  • 0
    A

    Why is it O(n)? Checking whether a word exist in the set and erase them probably takes more than O(1)


  • 0
    S

    Well, a HashSet should theoretically have O(1) amortized access time for an element


  • 0
    L
    This post is deleted!

  • 0
    L

    O(n^2) time. The worst situation is both startSet and endSet has 2/n words.


  • 0
    L

    Nice. I am using a similar way to do it to balance the 2-end neighbors' size and speed it up in C#.

    public int LadderLength(string start, string end, ISet<string> dict) {
        ISet<string> leftSet = new HashSet<string>(), rightSet = new HashSet<string>();
        leftSet.Add(start); rightSet.Add(end);
        dict.Remove(start); dict.Remove(end);
        int count = 1;
        while(leftSet.Count != 0) {
            count++;
            ISet<string> newLeftSet = new HashSet<string>();
            foreach(string word in leftSet) {
                StringBuilder sb = new StringBuilder(word);
                for(int i = 0; i < sb.Length; i++) {
                    char tmp = sb[i];
                    for(char ch = 'a'; ch <= 'z'; ch++) {
                        sb[i] = ch;
                        if(rightSet.Contains(sb.ToString())) return count;
                        if(dict.Contains(sb.ToString())) {
                            newLeftSet.Add(sb.ToString());
                            dict.Remove(sb.ToString());
                        }
                    }
                    sb[i] = tmp;
                }
            }
            if(rightSet.Count > newLeftSet.Count)
                leftSet = newLeftSet;
            else
            { leftSet = rightSet; rightSet = newLeftSet; }
        }
        return 0;
    }
    

  • 0
    E

    Great optimization. Thx for sharing!


Log in to reply
 

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