高明顺德网站建设,域名的购买费用,网络营销外包平台,广告制作的软件文章目录 一、题目二、解法三、完整代码 所有的LeetCode题解索引#xff0c;可以看这篇文章——【算法和数据结构】LeetCode题解。 一、题目 二、解法 思路分析#xff1a;示例1为例#xff0c;hit到达cog的路线不止一条#xff0c;如何找到最短是关键。广度优先搜索是一圈… 文章目录 一、题目二、解法三、完整代码 所有的LeetCode题解索引可以看这篇文章——【算法和数据结构】LeetCode题解。 一、题目 二、解法 思路分析示例1为例hit到达cog的路线不止一条如何找到最短是关键。广度优先搜索是一圈一圈的搜索过程一旦找到了结果一定是最短的。本题也只需要最短转换序列的数目而不需要具体的序列因此不用去关心下图中线是如何连在一起的。因此最终选择广搜只要差一个字符说明序列之间是连接的。
本题还是一个无向图需要用到标记位标记节点是否走过否则会陷入死循环。为此我们引入一个unordered_mapstring, int visitMap类型的地图记录word是否被访问过key值为单词value为beginWord到该单词的路径长度。集合是数组类型的提前转成集合set类型查找更快。 根据单词的长度每次替换其中一个单词需要用到两个循环一个循环选择单词中替换的字符位置另一个用来选择26个字母中的其中一个。然后在单词集合中查找是否存在替换之后的新单词如果找到将其加入visitMap中。如果新单词是endWord那么直接放回path1。path代表路径长度。 程序如下
// 127、单词接龙-深度优先搜索
class Solution {
public:int ladderLength(string beginWord, string endWord, vectorstring wordList) {unordered_setstring wordSet(wordList.begin(), wordList.end()); // 转成uset类型查找更快if (wordSet.find(endWord) wordSet.end()) return 0; // endWord没有在单词集合中出现直接返回0unordered_mapstring, int visitMap; // 记录word是否被访问过key值为单词value为beginWord到该单词的路径长度queuestring que; visitMap.insert(pairstring, int(beginWord, 1));que.push(beginWord);while (!que.empty()) {string word que.front();que.pop();int path visitMap[word]; // 路径长度for (int i 0; i word.size(); i) {string newWord word; // 用一个新单词替换word每次置换一个字母for (int j 0; j 26; j) {newWord[i] j a;if (newWord endWord) return path 1; // 找到endif (wordSet.find(newWord) ! wordSet.end() visitMap.find(newWord) visitMap.end()) { // newWord出现在wordSet中且没有访问过visitMap.insert(pairstring, int(newWord, path 1));que.push(newWord);}}}}return 0;}
};复杂度分析 时间复杂度 O ( N × C ) O(N \times C) O(N×C)N为wordList长度C为单词长度。字符串数组转化成umap字符串类型需要 O ( N ) O(N) O(N)。最坏情况下遍历到wordList最后一个元素才会找到endWordwhile循环中的一些操作如visitMap插入元素和que队列插入、弹出元素复杂度为 O ( N ) O(N) O(N)。两个for循环的复杂度为 O ( 26 × C ) O(26 \times C) O(26×C)。因此最终的复杂度为 O ( N × C ) O(N \times C) O(N×C)。 空间复杂度 O ( N × C ) O(N \times C) O(N×C)。
三、完整代码
// 127、单词接龙-深度优先搜索
class Solution {
public:int ladderLength(string beginWord, string endWord, vectorstring wordList) {unordered_setstring wordSet(wordList.begin(), wordList.end()); // 转成uset类型查找更快if (wordSet.find(endWord) wordSet.end()) return 0; // endWord没有在单词集合中出现直接返回0unordered_mapstring, int visitMap; // 记录word是否被访问过key值为单词value为beginWord到该单词的路径长度queuestring que; visitMap.insert(pairstring, int(beginWord, 1));que.push(beginWord);while (!que.empty()) {string word que.front();que.pop();int path visitMap[word]; // 路径长度for (int i 0; i word.size(); i) {string newWord word; // 用一个新单词替换word每次置换一个字母for (int j 0; j 26; j) {newWord[i] j a;if (newWord endWord) return path 1; // 找到endif (wordSet.find(newWord) ! wordSet.end() visitMap.find(newWord) visitMap.end()) { // newWord出现在wordSet中且没有访问过visitMap.insert(pairstring, int(newWord, path 1));que.push(newWord);}}}}return 0;}
};end
