Accepted C++ version in DBFS(61ms)


  • 2
    D

    My DBFS method is pretty effective. Share it with all of you guys.

     /*DBFS method, each time generate all reachable words in the dict that can be transformed from start in the ith steps, and delete this word in dict. 
    Terminate until reach the same word in the other frontier and return dist+1, or a queue is empty and the path does not exist.
        */
                    
        class Solution {
        public:
            public:
                int ladderLength(string start, string end, unordered_set<string> &dict) {
                    queue<string> q1, q2, q3;                        // q1, q2 are the queues for two ends
                    unordered_set<string>   frontier1, frontier2;       //frontier1, frontier2 store words that were just reached on both ends
                    int dist = 1;
                    q1.push(start); q2.push(end);
                    frontier1.insert(start); frontier2.insert(end);
                    
                    while ( !q1.empty() && !q2.empty()) {       //If one queue is empty, no connection can be built
                        
                        if(q1.size() <= q2.size()){
                            frontier1.clear();
                            while(!q1.empty()){
                                string word = q1.front(); q1.pop();
                                for (int i = 0; i < word.size(); i++) {
                                    string temp = word;
                                    for (char c = 'a'; c <= 'z'; c++) {
                                        if(c==word[i])  continue;
                                        temp[i] =c;
                                        
                                        if(frontier2.count(temp) > 0)     return dist+1;
                                        
                                        if (dict.count(temp) > 0) {
                                        //use q3 to store the intermediate words that can be reached in the next step
                                            q3.push(temp);         
                                            dict.erase(temp);
                                            frontier1.insert(temp);
                                        }
                                    }
                                }
                            }
                            dist++;
                            swap(q1, q3);
                        }
                        else{
                            frontier2.clear();
                            while(!q2.empty()){
                                string word = q2.front(); q2.pop();
                                for (int i = 0; i < word.size(); i++) {
                                    string temp = word;
                                    for (char c = 'a'; c <= 'z'; c++) {
                                        if(c==word[i])  continue;
                                        temp[i] =c;
                                        
                                        if(frontier1.count(temp) > 0)     return dist+1;
                                        
                                        if (dict.count(temp) > 0) {
                                            //use q3 to store the intermediate words that can be reached in the next step
                                            q3.push(temp);          
                                            dict.erase(temp);
                                            frontier2.insert(temp);
                                        }
                                    }
                                }
                            }
                            dist++;
                            swap(q2, q3);
                        }
                        
                    }
                    return 0;
                }
        };

  • 0
    J

    Thank you for sharing! That's so brilliant!

    I rewrote your solution and used a common function to handle "stepping forward", either from start or end.

    Cheers!

    class Solution {
    public:
        int ladderLength(string start, string end, unordered_set<string> &dict) {
            queue<string> fromStart, fromEnd;
            unordered_set<string> frontierStart, frontierEnd;
            fromStart.push(start);
            fromEnd.push(end);
            frontierStart.insert(start);
            frontierEnd.insert(end);
            int dist=1;
    
            while(!fromStart.empty()&&!fromEnd.empty()){
                if(fromStart.size()<=fromEnd.size()){
                    if(stepForward(fromStart, dict, frontierStart, frontierEnd)) return dist + 1;
                }else{
                    if(stepForward(fromEnd, dict, frontierEnd, frontierStart)) return dist + 1;
                }
                dist++;
            }
            return 0;
        }
        bool stepForward(queue<string> &levelQ, unordered_set<string> &dict,
                            unordered_set<string> &frontSelf, unordered_set<string> &frontOther){
            queue<string> nextLevelQ;
            frontSelf.clear();
            while(!levelQ.empty()){
                string currWord = levelQ.front(); levelQ.pop();
                for(int i=0;i<currWord.size();i++){
                    for(char newC='a';newC<='z';newC++){
                        string nextWord=currWord;
                        nextWord[i]=newC;
                        if(frontOther.count(nextWord)>0) return true;
                        if(dict.count(nextWord)>0){
                            dict.erase(nextWord);
                            nextLevelQ.push(nextWord);
                            frontSelf.insert(nextWord);
                        }
                    }            
                }
            }
            levelQ.swap(nextLevelQ);
            return false;
        }
    };
    

  • 0
    M

    great idea!avoid words compare.


  • 0
    N

    q1,q2 is useless, u can use frontier1 and frontier2 directly. And bro, it's not DFS, it's BFS.


Log in to reply
 

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