题目描述

Word Ladder

[HARD]

A transformation sequence from word beginWord to word endWord using a dictionary wordList is a sequence of words beginWord -> s1 -> s2 -> … -> sk such that:

  • Every adjacent pair of words differs by a single letter.
  • Every si for 1 <= i <= k is in wordList. Note that beginWord does not need to be in wordList.
  • sk == endWord

Given two words, beginWord and endWord, and a dictionary wordList, return the number of words in the shortest transformation sequence from beginWord to endWord, or 0 if no such sequence exists.

Example

1
2
3
4
5
6
7
Input
beginWord = "hit",
endWord = "cog",
dict = ["hot","dot","dog","lot","log","cog"]

Output
5

思路

BFS

所以当我们从一个单词（比如 “hit”）出发时，要做的就是：

  • 枚举这个单词的每一个位置
  • 尝试把该位置的字母换成 ‘a’ ~ ‘z’ 的任意一个字母
  • 如果换完后得到的单词在字典 wordSet 中，就说明这是一个有效的下一步

  1. 起点入队：beginWord，步数为 1。

  2. 队列循环：

  • 取出当前单词 word。

  • 如果它等于 endWord，返回步数。

  • 否则生成所有一字母变化的邻居（上面那段 for (char c = ‘a’; … )）.

  • 把有效的邻居（在字典里的）加入队列，并从字典中删掉(防止重复访问).

  1. 如果队列空了还没找到，返回 0

代码

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
33
34
35
36
37
38
39
40
41
class Solution {
public:
    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
        unordered_set<string> dict(wordList.begin(), wordList.end());
        if(!dict.count(endWord)) {
            return 0; // endWord not in wordList
        }

        queue<pair<string,int>> q;
        q.push({beginWord, 1}); // {word, length}

        unordered_set<string> visited;

        visited.insert(beginWord);

        while(!q.empty()){
            auto [word, length] = q.front(); q.pop();

            for(int i = 0; i < word.size(); ++i) {

                string tmp = word;
                for(char c = 'a'; c <= 'z'; ++c) {
                    
                    tmp[i] = c;


                    if(tmp == endWord) {
                        return length + 1; // Found the endWord
                    }

                    if(dict.count(tmp) && !visited.count(tmp)) {
                        visited.insert(tmp);
                        q.push({tmp, length + 1});
                    }
                }
            }
        }

        return 0;
    }
};