xml的网站地图织梦制作,产品设计五个流程,python 网站开发 实例,wordpress cos存储文章目录1. 题目2. 图的BFS解题2.1 单向BFS2.2 双向BFS #xff01;厉害了1. 题目
给定两个单词#xff08;beginWord 和 endWord#xff09;和一个字典#xff0c;找到从 beginWord 到 endWord 的最短转换序列的长度。 转换需遵循如下规则#xff1a;
每次转换只能改变…
文章目录1. 题目2. 图的BFS解题2.1 单向BFS2.2 双向BFS 厉害了1. 题目
给定两个单词beginWord 和 endWord和一个字典找到从 beginWord 到 endWord 的最短转换序列的长度。 转换需遵循如下规则
每次转换只能改变一个字母。转换过程中的中间单词必须是字典中的单词。
说明: 如果不存在这样的转换序列返回 0。 所有单词具有相同的长度。 所有单词只由小写字母组成。 字典中不存在重复的单词。 你可以假设 beginWord 和 endWord 是非空的且二者不相同。
示例 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 不在字典中所以无法进行转换。来源力扣LeetCode 链接https://leetcode-cn.com/problems/word-ladder 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。
2. 图的BFS解题
题目有点恶心的地方在于beginWord不知道是不是在list内需要判断 类似题目 程序员面试金典 - 面试题 17.22. 单词转换BFS LeetCode 126. 单词接龙 II图的BFS
2.1 单向BFS
利用队列进行BFS
class Solution {
public:int ladderLength(string beginWord, string endWord, vectorstring wordList) {int len wordList.size(), i, k, n, lv 0;unordered_mapstring,int m;bool visited[len] {false};for(i 0; i len; i){m[wordList[i]] i;if(wordList[i] beginWord)visited[i] true;}if(m.find(endWord) m.end())return 0;queuestring q;string str;q.push(beginWord);while(!q.empty()){lv;n q.size();while(n--){for(i 0; i beginWord.size(); i){//对每个单词的每个字符进行改变str q.front();for(k 1; k 25; k){str[i] 1;if(str[i] z)str[i] a;if(m.find(str) ! m.end() !visited[m[str]]){ //在集合中且没有访问的q.push(str);visited[m[str]] true;if(str endWord)return lv1;}}}q.pop();}}return 0;}
};2.2 双向BFS 厉害了 从起始和终点分别开始BFS2个队列visited 存储int值初始化为0正向访问了1反向访问了2如果某个visited的值为3说明都访问到了连通了每次选择队列较短的一端继续BFS减少队列扩大的规模提高效率
class Solution {
public:int ladderLength(string beginWord, string endWord, vectorstring wordList) {int len wordList.size(), wlen beginWord.size(), i, k, n, n1, n2, flag, lv 0;unordered_mapstring,int m;vectorint visited(len,0);bool beginWordInList false;for(i 0; i len; i){m[wordList[i]] i;if(wordList[i] beginWord)//判断beginWord在List中否{visited[i] 1;//beginWord正向访问beginWordInList true;}}if(!beginWordInList)//beginWord不在list中{visited.push_back(1);//添加起点正向访问值为1m[beginWord] len;//哈希表添加}if(m.find(endWord) m.end())return 0;queuestring q1, q2;string str;q1.push(beginWord);q2.push(endWord);visited[m[endWord]] 2;//终点反向访问了值为2while(!q1.empty() !q2.empty()){lv;//走的步数n1 q1.size();n2 q2.size();queuestring Q n1n2 ? q1 : q2;//Q是较短的队列的引用flag n1n2 ? 1 : 2;//访问后增加的值n Q.size();while(n--){for(i 0; i wlen; i){str Q.front();for(k 1; k 25; k){str[i] 1;if(str[i] z)str[i] a;if(m.find(str) ! m.end() visited[m[str]] ! flag){ //不等于1说明正向没有访问不等于2说明反向没有访问Q.push(str);visited[m[str]] flag;if(visited[m[str]] 3)//等于3说明双向访问过找到路径return lv1;}}}Q.pop();}}return 0;}
};
