网站颜色 字体,代销网站源码,网站运营策略如何做,网络优化工程师有多累目录
③力扣127. 单词接龙
解析代码 ③力扣127. 单词接龙
127. 单词接龙
难度 困难
字典 wordList 中从单词 beginWord 和 endWord 的 转换序列 是一个按下述规格形成的序列 beginWord - s1 - s2 - ... - sk#xff1a;
每一对相邻的单词只差一个字母。…目录
③力扣127. 单词接龙
解析代码 ③力扣127. 单词接龙
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 10endWord.length beginWord.length1 wordList.length 5000wordList[i].length beginWord.lengthbeginWord、endWord 和 wordList[i] 由小写英文字母组成beginWord ! endWordwordList 中的所有字符串 互不相同
class Solution {
public:int ladderLength(string beginWord, string endWord, vectorstring wordList) {}
}; 解析代码 和力扣433. 最小基因变化一样如果将每次字符串的变换抽象成图中的两个顶点和一条边的话问题就变成了边权为 1 的最短路问题。 因此从起始的字符串开始来一次 bfs 即可。
class Solution {
public:int ladderLength(string beginWord, string endWord, vectorstring wordList) {unordered_setstring wordListHash(wordList.begin(), wordList.end());unordered_setstring vis;if(!wordListHash.count(endWord))return 0;int ret 1;queuestring q;q.push(beginWord);vis.insert(beginWord);while(!q.empty()){ret;int size q.size();while(size--){string t q.front();q.pop();for(int i 0; i t.size(); i){for(char ch a; ch z; ch){string tmp t;tmp[i] ch;if(wordListHash.count(tmp) !vis.count(tmp)){if(tmp endWord)return ret;q.push(tmp);vis.insert(tmp);}}}}}return 0;}
};
