126

class Solution {
public:
    vector<vector<string>> findLadders(string beginWord, string endWord, vector<string>& wordList) {
        unordered_map<string, int> m;
        unordered_map<int, string> revm;
        int count = 1;
        for(string word: wordList){
            m[word] = count++;
            revm[count-1] = word;
        }
        if(!m.count(beginWord)){
            m[beginWord] = count++;
            revm[count-1] = beginWord;
        }

        // Create graph.
        vector<vector<int>> graph(count);
        for(auto p: m){
            string word = p.first;
            int wordIdx = p.second;
            for(int i=0; i<word.length(); i++){
                for(int j=1; j<26; j++){
                    string nextWord = word;
                    nextWord[i] = (nextWord[i]-'a'+j)%26 + 'a';
                    if(m.count(nextWord)){
                        graph[wordIdx].push_back(m[nextWord]);
                    }
                }
            }
        }

        // Do BFS.
        vector<vector<int>> idx;
        if(!m.count(endWord)) return vector<vector<string>>();
        queue<pair<int, vector<int>>> q;
        int source = m[beginWord];
        vector<int> seq = {source};
        vector<bool> vis(count, false);
        q.push({source, seq});
        int dest = m[endWord];

        while(!q.empty()){
            int sz = q.size();
            unordered_set<int> curVis;
            for(int i=0; i<sz; i++){
                auto p = q.front(); q.pop();
                int curr = p.first;
                for(int child: graph[curr]){
                    if(vis[child]) continue;
                    vector<int> nextSeq(p.second);
                    nextSeq.push_back(child);
                    if(child == dest){
                        idx.push_back(nextSeq);
                        break;
                    }
                    q.push({child, nextSeq});
                    curVis.insert(child);
                }
            }
            if(idx.size()) break;
            for(auto it=curVis.begin(); it != curVis.end(); it++){
                vis[*it] = true;
            }
        }
        vector<vector<string>> ans;
        for(auto vec: idx){
            vector<string> path;
            for(auto i: vec)
                path.push_back(revm[i]);
            ans.push_back(path);
        }
        return ans;
    }
};