127. 单词接龙

Difficulty: 困难

字典 wordList 中从单词 beginWord和 endWord 的 转换序列 是一个按下述规格形成的序列：

  • 序列中第一个单词是 beginWord 。
  • 序列中最后一个单词是 endWord 。
  • 每次转换只能改变一个字母。
  • 转换过程中的中间单词必须是字典 wordList 中的单词。

给你两个单词beginWord和 endWord 和一个字典 wordList ，找到从 beginWord 到 endWord 的 最短转换序列 中的 单词数目 。如果不存在这样的转换序列，返回 0。

示例 1：

1
2
3

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

示例 2：

1
2
3

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

提示：

  • 1 <= beginWord.length <= 10
  • endWord.length == beginWord.length
  • 1 <= wordList.length <= 5000
  • wordList[i].length == beginWord.length
  • beginWord、endWord 和 wordList[i] 由小写英文字母组成
  • beginWord != endWord
  • wordList 中的所有字符串 互不相同

Solution

Language: ****

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

class Solution {
public:
    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
        unordered_set<string> ws(wordList.begin(),wordList.end() );
        queue<string> q;
        unordered_map<string,int> dist;

        q.push(beginWord);
        dist[beginWord] = 0;
        while(q.size()) {
            string curNode = q.front() ;  q.pop();
            string nextNode;
            int n = curNode.size();
            for(int i=0;i<n;++i) {
                nextNode = curNode;
                for(char j='a';j<='z';j++) {
                    nextNode[i] = j;
                    if(!ws.count(nextNode)) continue;
                    if(dist.count(nextNode)) continue;
                    dist[nextNode] = dist[curNode] + 1;
                    if(nextNode == endWord) {
                        return dist[nextNode] + 1;
                    }
                    q.push(nextNode);

                }
            }
        }
        return 0;

    }
};