leetcode-127：单词接龙

输入：beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]
输出：5
解释：一个最短转换序列是 "hit" -> "hot" -> "dot" -> "dog" -> "cog", 返回它的长度 5。

输入：beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log"]
输出：0
解释：endWord "cog" 不在字典中，所以无法进行转换。

class Solution {
public:
    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
        unordered_set<string> wordSet(wordList.begin(),wordList.end());
        if(wordSet.count(endWord)==0) return 0;
        unordered_map<string,int> mp;  //<word, 查询到这个word路径长度>
        queue<string> q;
        q.push(beginWord);
        mp[beginWord]=1;
        while(!q.empty()){
            string cur=q.front();
            q.pop();
            int path=mp[cur];
            for(int i=0;i<cur.size();i++){
                string next=cur;
                for(int j=0;j<26;j++){
                    next[i]=j+'a';
                    if(next==endWord) return path+1;
                    if(wordSet.count(next)&&mp.count(next)==0){// wordSet出现了next，并且next没有被访问过
                        mp[next]=path+1;
                        q.push(next);
                    }
                }
            }
        }
        return 0;
    }
};