360免费建站空间,陕西购物商城网站建设,媒介星软文平台,免费购物平台都有哪些127. 单词接龙
字典 wordList 中从单词 beginWord 和 endWord 的 转换序列 是一个按下述规格形成的序列 beginWord - s1 - s2 - ... - sk#xff1a;
每一对相邻的单词只差一个字母。对于 1 i k 时#xff0c;每个 si 都在 wordList 中。注意 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 10endWord.length beginWord.length1 wordList.length 5000wordList[i].length beginWord.lengthbeginWord、endWord 和 wordList[i] 由小写英文字母组成beginWord ! endWordwordList 中的所有字符串 互不相同
题解思路
在学习图论的时候做的一道题完全没有思路之前做的题都是二维矩阵有个图样轮到每个点有四个方向供我选择这道题只有一个单词列表。
待解决问题 深搜or广搜 如何建图
广搜
这道题应该用广度搜索题目中要求最短路径用广搜的话如果遍历到了则就是那么对应的路径就是最短路径
关于建图
之前是有一个图然后我们遍历到每一个点后尝试该点的四个方向
这道题没有图我们遍历到一个单词后该如何尝试方向呢
题目要求每次只改变一个单词的一个字母且改变后的单词需要出现在wordlist中我们就可以基于改变一个字母来确定遍历的方向
遍历方向为
到每一个单词时有word_length*26个方向供我们遍历
while(!que.empty()){string word que.front(); que.pop();int path visited[word]; // unordered_mapfor(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()){pairint, 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 终止条件处理}
}通过广搜框架我们不需要显示的建图就可以像图一样搜索。
完整代码
class Solution {
public:int ladderLength(string beginWord, string endWord, vectorstring wordList) {unordered_setstring wordSet(wordList.begin(), wordList.end());if(wordSet.find(endWord) wordSet.end()) return 0;unordered_mapstring, int visited;visited[beginWord] 1;queuestring 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;}
};
