C++ BFS solution with search 0(26 * word.length() ) wordList removed by step of bfs


  • 0
    A

    class Solution {
    public:

    vector<vector<string>> findLadders(string beginWord, string endWord, unordered_set<string> &wordList) {
        vector<vector<string>> ans;
        vector<string> path;
        vector <string> next;
                    
        vector< pair<string, pair<int, int> > > bfs;
        int st = 0, fin = 0, k, last = 0;
        
        if (beginWord == "" || beginWord == endWord) return ans;
        wordList.insert(endWord);
        //worst case : path consist of all words 
        int min = wordList.size();
        
        next.push_back(beginWord);
        
        bfs.push_back( make_pair (beginWord, make_pair(1, -1)) );
        while( st <= fin && min > bfs[st].second.first ){
            if (last != bfs[st].second.first ) {
                last = bfs[st].second.first;
                for (int i=0; i<next.size(); i++)
                    wordList.erase(next[i]);
                next.clear();    
            }
    
            //cout<<bfs[st].first<<" "<<bfs[st].second.first<<" "<<bfs[st].second.second<<endl;
            
            string nextWord;
            beginWord = bfs[st].first;
            //nextWords all set next[i], bfs[st].second.first + 1, st     
            
            for (int i=0; i<beginWord.length(); i++){
                nextWord = beginWord;
                for (int j=0; j<26; j++){
                    nextWord[i] = 'a'+ j;
    
                    auto it = wordList.find(nextWord);
                    if (it != wordList.end() && nextWord != beginWord ) {
                        next.push_back(nextWord);
                        fin++;
                        bfs.push_back( make_pair (nextWord, make_pair(bfs[st].second.first + 1, st)) );
                        if (nextWord == endWord){
                            //cout<<fin<<endl;
                            min = bfs[st].second.first + 1;
                            path.clear();
                            k = fin;
                            while(bfs[k].second.second != -1){
                                path.push_back( bfs[k].first );
                                k = bfs[k].second.second;
                            }                    
                            path.push_back( bfs[k].first );
                            //cout<<endl<<path.size()<< ": ";
                            reverse( path.begin(), path.end() );
                            // for (k = 0; k < path.size(); k++){
                            //     cout<<path[k]<<" ";
                            // }
                            ans.push_back(path);
                        }
                    }
                }
            }
            st++;
        }
    
        return ans;
    }
    

    };


Log in to reply
 

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