丹徒网站建设包括哪些,有什么做衣服的网站吗,电子商务网站建设文档,江夏区建设局网站1. 题目
给定两个单词#xff08;beginWord 和 endWord#xff09;和一个字典 wordList#xff0c;找出所有从 beginWord 到 endWord 的最短转换序列。
转换需遵循如下规则#xff1a;
每次转换只能改变一个字母。转换过程中的中间单词必须是字典中的单词。
说明: 如果…1. 题目
给定两个单词beginWord 和 endWord和一个字典 wordList找出所有从 beginWord 到 endWord 的最短转换序列。
转换需遵循如下规则
每次转换只能改变一个字母。转换过程中的中间单词必须是字典中的单词。
说明: 如果不存在这样的转换序列返回一个空列表。 所有单词具有相同的长度。 所有单词只由小写字母组成。 字典中不存在重复的单词。 你可以假设 beginWord 和 endWord 是非空的且二者不相同。
示例 1:
输入:
beginWord hit,
endWord cog,
wordList [hot,dot,dog,lot,log,cog]
输出:
[[hit,hot,dot,dog,cog],[hit,hot,lot,log,cog]
]示例 2:
输入:
beginWord hit
endWord cog
wordList [hot,dot,dog,lot,log]
输出: []
解释: endWord cog 不在字典中所以不存在符合要求的转换序列。来源力扣LeetCode 链接https://leetcode-cn.com/problems/word-ladder-ii 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。
类似题目 LeetCode 127. 单词接龙图的BFS/双向BFS 程序员面试金典 - 面试题 17.22. 单词转换BFS
2. BFS解题
详见注释
class Solution {
public:vectorvectorstring findLadders(string beginWord, string endWord, vectorstring wordList) {vectorvectorstring ans;unordered_setstring wlist(wordList.begin(),wordList.end());unordered_setstring words;//存放当次被加入到路径的单词queuevectorstring q;//队列里存放的是可行的路径q.push({beginWord});words.insert(beginWord);int level 1, minLevel INT_MAX, n, i;vectorstring frontPath, newPath;string lastWordOfPath, newLastWord;char ch;while(!q.empty()){n q.size();while(n--){frontPath q.front();//vectorstringq.pop();//frontPath出队if(frontPath.size() level)//下一个level时进入{for(string word:words) wlist.erase(word);//将上一个lv进入路径的单词从集合中删除words.clear();level frontPath.size();//level1if(level minLevel) //如果level比最小的还大没必要进行下去break;}lastWordOfPath frontPath.back();for(i 0; i lastWordOfPath.size(); i){ //根据最后一个单词衍生新的单词newLastWord lastWordOfPath;for(ch a; ch z; ch){newLastWord[i] ch;if(!wlist.count(newLastWord)) //新单词不在集合中,下一个continue;words.insert(newLastWord);//在集合中加入路径并记录在wordsnewPath frontPath;//vectorstringnewPath.push_back(newLastWord);if(newLastWord endWord){ans.push_back(newPath);minLevel level;}elseq.push(newPath);}}}}return ans;}
};
