leetcode127单词接龙刷题打卡-Toy模板网

这篇具有很好参考价值的文章主要介绍了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。

示例 2：

输入：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 中的所有字符串 互不相同

题解思路

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

待解决问题：

深搜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 终止条件处理
        }
        
    }
}

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

while(!que.empty()){
    pair<int, int> 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 终止条件处理
        
    }
}

通过广搜框架我们不需要显示的建图就可以像图一样搜索。文章来源地址https://www.toymoban.com/news/detail-702148.html

完整代码

class Solution {
public:
    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
        unordered_set<string> wordSet(wordList.begin(), wordList.end());
        if(wordSet.find(endWord) == wordSet.end()) return 0;
        unordered_map<string, int> visited;
        visited[beginWord] = 1;
        queue<string> 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;
        
    }
};

到了这里，关于leetcode127单词接龙刷题打卡的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！