Untitled

class Solution {
public:
    vector<vector<int> > createGraph(vector<string>& wl){
        vector<vector<int> > graph(wl.size());
        map<string, vector<int> > mp;
        int l = wl[0].length();
        for(int i=0;i<l;i++){
            mp.clear();
            for(int j = 0;j<wl.size();j++){
                string s = wl[j].substr(0,i) + wl[j].substr(i+1, l-i-1);
                mp[s].push_back(j);
            }
            for(auto it:mp){
                for(auto i:it.second){
                    for(auto j:it.second){
                        if(i!=j)
                            graph[i].push_back(j);
                    }
                }
            }
        }
        return graph;
    }
    vector<vector<string>> findLadders(string beginWord, string endWord, vector<string>& wordList) {
        wordList.push_back(beginWord);
        vector<vector<int> > graph = createGraph(wordList);
        
        //bfs
        queue<vector<int> > que;
        que.push({(int(wordList.size()-1))});
        vector<int> vis(wordList.size(), INT_MAX);
        
        vector<vector<string> > ans;
        while(!que.empty()){
            vector<int> p = que.front();
            que.pop();
            if(vis[p[p.size()-1]]<p.size()) continue;
            vis[p[p.size()-1]] = p.size();
            // cout<<p[p.size()-1]<<' '<<p.second<<endl;
            if(wordList[p[p.size()-1]] == endWord){
                if(ans.size()!=0 && ans[0].size()<p.size()){
                    break;
                }
                vector<string> temp;
                for(auto i:p){
                    temp.push_back(wordList[i]);
                }
                ans.push_back(temp);
            }
            for(auto node: graph[p[p.size()-1]]){
                vector<int> temp = p;
                temp.push_back(node);
                que.push(temp);
            }
        }
        return ans;
    }
};