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;
    }
    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
        wordList.push_back(beginWord);
        vector<vector<int> > graph = createGraph(wordList);
        
        //bfs
        queue<pair<int,int> > que;
        que.push(make_pair(wordList.size()-1, 1));
        vector<int> vis(wordList.size(), 0);
        while(!que.empty()){
            pair<int,int> p = que.front();
            que.pop();
            if(vis[p.first]!=0) continue;
            vis[p.first] = 1;
            cout<<p.first<<' '<<p.second<<endl;
            if(wordList[p.first] == endWord) return p.second;
            for(auto node: graph[p.first]){
                que.push(make_pair(node, p.second+1));
            }
        }
        return 0;
    }
};