39ms C++ Two End BFS Recursive Solution (> 99%)


  • 1
    M

    Basically same idea as other two ended BFS solutions, but I might used some lower overhead operations and less calculations.

    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
            unordered_set<string> s1, s2, wlist;
            s1.insert(beginWord);
            s2.insert(endWord);
            for(string w : wordList){
                wlist.insert(w);
            }
            if(wlist.count(endWord) == 0){
                return 0;
            }
            return find(s1, s2, wlist, 0);
        }
        
    int find(unordered_set<string>& s1, unordered_set<string>& s2, unordered_set<string>& wlist, int len){
            
            unordered_set<string> next;
            for(string s : s1){
                wlist.erase(s);
                if(s2.count(s) > 0){
                    return len + 1;
                }
                for(int i = 0; i < s.length(); ++i){
                    char cur = s[i];
                    for(char c = 'a'; c <='z'; ++c){
                        if(c == cur){
                            continue;
                        }
                        s[i] = c;
                        if(wlist.count(s) > 0){
                            next.insert(s);
                        }
                        s[i] = cur;  
                    }
                }
            }
            s1 = next;
            if(s1.empty()){
                return 0;
            }
            if(s2.size() < s1.size()){
                return find(s2, s1, wlist, len + 1);
            }
            return find(s1, s2, wlist, len + 1);
        }
    

  • 0
    R
    This post is deleted!

Log in to reply
 

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