Very Easy BFS Problem, without constructing graph (BFS on paths)


#1

Just perform normal bfs on vector of words with some tweaks.

vector<vector<string> > Solution::findLadders(string beginWord, string endWord, vector<string>& wordList) {
    // Do not write main() function.
    // Do not read input, instead use the arguments to the function.
    // Do not print the output, instead return values as specified
    // Still have a doubt. Checkout www.interviewbit.com/pages/sample_codes/ for more details
        if(beginWord==endWord)
            return {{beginWord}};
        unordered_set <string> list(wordList.begin() , wordList.end());
        
        list.insert(endWord);
        vector < vector<string>> final_ans;
        
        queue<vector<string>>que;
        que.push({beginWord});
        
        while(!que.empty()){
            
            int size=que.size();
            bool find=0;
            unordered_set<string>visited;
            while(size--){
                auto curr=que.front();
                string word=curr.back();
                que.pop();
                for(int i=0;i<word.length();i++){
                    for(char j='a';j<='z';j++){
                       string temp=word;
                        temp[i]=j;
                        if(list.count(temp)){
                            curr.push_back(temp);
                            if(temp==endWord){
                                final_ans.push_back(curr);
                                find=1;
                            }else que.push(curr);
                            visited.insert(temp);
                            curr.pop_back();
                        }
                    }
                    
                }
            }
            for(auto x:visited){
                if(list.count(x))
                    list.erase(x);
            }
            
            if(find)break;
            
        }
        return final_ans;
}