C++ BFS easy to understand (UPDATED version)


  • 1
        int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
            unordered_map<string,vector<string>>graph(wordList.size());
            deque<string>cur;  //current level
            deque<string>next;  //next level
            cur.push_back(beginWord);
            int length=2;
            while(!cur.empty()){
                string s=cur.front();
                cur.pop_front();
                for(int i=0;i<wordList.size();){
                    if(transformable(s,wordList[i]))
                        if(wordList[i]==endWord) return length;
                        else graph[s].push_back(wordList[i]),wordList.erase(wordList.begin()+i);
                    else i++;
                }
                for(auto x:graph[s]) next.push_back(x);
                if(cur.empty()&&!next.empty()) swap(cur,next),length++;
            }
            return 0;
        }
        
        bool transformable(string s1,string s2){
            int diff=0;
            for(int i=0;i<s1.size();i++)
                if(s1[i]!=s2[i]) diff++;
            return diff==1;
        }
    

Log in to reply
 

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