leetcode127单词接龙刷题打卡

127. 单词接龙

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

• 每一对相邻的单词只差一个字母。
• 对于 1 <= i <= k 时，每个 si 都在 wordList 中。注意， beginWord 不需要在 wordList 中。
• sk == endWord

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

示例 1：

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

示例 2：

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

提示：

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

题解思路

在学习图论的时候做的一道题，完全没有思路，之前做的题都是二维矩阵，有个图样，轮到每个点有四个方向供我选择，这道题只有一个单词列表。

待解决问题：

• 深搜or广搜

• 如何建图

广搜

这道题应该用广度搜索，题目中要求最短路径，用广搜的话如果遍历到了则就是那么对应的路径就是最短路径

关于建图

之前是有一个图，然后我们遍历到每一个点后尝试该点的四个方向，

这道题没有图我们遍历到一个单词后该如何尝试方向呢？

题目要求每次只改变一个单词的一个字母且改变后的单词需要出现在wordlist中，我们就可以基于改变一个字母来确定遍历的方向

遍历方向为：

到每一个单词时，有word_length*26个方向供我们遍历

while(!que.empty()){
    string word = que.front(); que.pop();
    int path = visited[word]; // unordered_map
    
    for(int i = 0; i < word.size(); i++){
        
        string newWord = word;
        for(int j = 0; j < 26; j++){
            newWord[i] = j + 'a';
            // 入队处理 and 终止条件处理
        }
        
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

我们对比一些二维矩阵的广搜核心框架

while(!que.empty()){
    pair cur = que.front(); que.pop();
    int curx = cur.first;
    int cury = cur.second;
    
    for(int i = 0; i < 4; i++){
        
        int nextx = curx + dir[i][0];
        int nexty = cury + dir[i][1];
        // 入队处理 and 终止条件处理
        
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13

通过广搜框架我们不需要显示的建图就可以像图一样搜索。

完整代码

class Solution {
public:
    int ladderLength(string beginWord, string endWord, vector& wordList) {
        unordered_set wordSet(wordList.begin(), wordList.end());
        if(wordSet.find(endWord) == wordSet.end()) return 0;
        unordered_map visited;
        visited[beginWord] = 1;
        queue que;
        que.push(beginWord);
        
        while(!que.empty()){
            string word = que.front(); que.pop();
            int path = visited[word];
            for(int i = 0; i < word.size(); i++){
                string newWord = word;
                for(int j = 0; j < 26; j++){
                    newWord[i] = j + 'a';
                    if(newWord == endWord) return path + 1;
                    if(wordSet.find(newWord) != wordSet.end() 
                            && visited.find(newWord)  == visited.end()){
                        visited[newWord] = path + 1;
                        que.push(newWord);
                    }
                }
            }
        }
        return 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