127 单词接龙

https://leetcode.cn/leetbook/read/top-interview-questions-hard/xwjmmm/

cost: 39m42s

class Solution {
public:
    int ladderLength(string beginWord, string endWord,
                     vector<string>& wordList) {
        unordered_map<string, int> wordIds;
        unordered_map<int, unordered_set<int>> graph;
        int idCounter = 0;
        wordList.push_back(beginWord);
        for (const string& word : wordList) {
            if (!wordIds.count(word)) {
                wordIds[word] = ++idCounter;
            }
            for (int i = 0; i < word.size(); i++) {
                string tmp = word;
                tmp[i] = '*';
                if (!wordIds.count(tmp)) {
                    wordIds[tmp] = ++idCounter;
                }
                int id = wordIds[word];
                int id2 = wordIds[tmp];
                graph[id].insert(id2);
                graph[id2].insert(id);
            }
        }

        auto it = wordIds.find(endWord);
        if (it == wordIds.end()) {
            return 0;
        }
        int endId = it->second;
        queue<int> q;
        q.push(wordIds[beginWord]);
        unordered_map<int, int> dist = {{wordIds[beginWord], 0}};

        while (!q.empty()) {
            int id = q.front();
            q.pop();
            if (id == endId) {
                return dist[id] / 2 + 1;
            }

            for (const int wordId : graph[id]) {
                if (!dist.count(wordId)) {
                    q.push(wordId);
                    dist[wordId] = dist[id] + 1;
                }
            }
        }
        return 0;
    }
};