127

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

        // 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.
        if(!m.count(endWord)) return 0;
        queue<int> q;
        vector<bool> vis(count, false);
        int source = m[beginWord];
        q.push(source); vis[source] = true;
        int ans = 1;
        int dest = m[endWord];
        while(!q.empty()){
            int sz = q.size();
            for(int i=0; i<sz; i++){
                int curr = q.front(); q.pop();
                for(int child: graph[curr]){
                    if(child == dest)
                        return ans+1;
                    if(!vis[child]){
                        vis[child] = true;
                        q.push(child);
                    }
                }
            }
            ans++;
        }
        return 0;
    }
};