❤️❤️❤️ 欢迎来到我的博客。希望您能在这里找到既有价值又有趣的内容，和我一起探索、学习和成长。欢迎评论区畅所欲言、享受知识的乐趣！
- 推荐：数据分析螺丝钉的首页 格物致知 终身学习 期待您的关注
- 导航：
- LeetCode解锁1000题: 打怪升级之旅：每题都包括3-5种算法，以及详细的代码实现，刷题面试跳槽必备
- 漫画版算法详解：通过漫画的形式和动态GIF图片把复杂的算法每一步进行详细可视解读，看一遍就掌握
- python源码解读：解读python的源代码与调用关系，快速提升代码质量
- python数据分析可视化：企业实战案例：企业级数据分析案例与可视化，提升数据分析思维和可视化能力
- 程序员必备的数学知识与应用：全面详细的介绍了工程师都必备的数学知识
期待与您一起探索技术、持续学习、一步步打怪升级 欢迎订阅本专栏❤️❤️
题目描述
给定两个单词（beginWord 和 endWord）和一个字典 wordList，找出所有从 beginWord 到 endWord 的最短转换序列的转换过程，转换需遵循如下规则：
- 每次转换只能改变一个字母。
- 转换过程中的中间单词必须在字典
wordList中。
说明:
- 如果不存在这样的转换序列，返回一个空列表。
- 所有单词具有相同的长度。
- 所有单词只包含小写字母。
- 字典
wordList是非空的，且不包含重复的单词。 beginWord和endWord是非空的，且不相同。
示例:
输入:
beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]
输出:
[ ["hit","hot","dot","dog","cog"], ["hit","hot","lot","log","cog"]
方法一：广度优先搜索（BFS）+ 回溯
解题步骤
- 使用 BFS 确定最短路径长度并记录每个单词的所有可能前驱词。
- 从
endWord开始，使用回溯法根据前驱词列表构造所有有效路径。
Python 示例
from collections import defaultdict, deque def findLadders(beginWord, endWord, wordList): if endWord not in wordList: return [] wordList = set(wordList) layer = {} layer[beginWord] = [[beginWord]] while layer: newlayer = defaultdict(list) for word in layer: if word == endWord: return layer[word] for i in range(len(word)): for c in 'abcdefghijklmnopqrstuvwxyz': newword = word[:i] + c + word[i+1:] if newword in wordList: newlayer[newword] += [j + [newword] for j in layer[word]] wordList -= set(newlayer.keys()) layer = newlayer return [] # Example usage beginWord = "hit" endWord = "cog" wordList = ["hot","dot","dog","lot","log","cog"] print(findLadders(beginWord, endWord, wordList))
算法分析
- 时间复杂度: O(N * M^2)，N 是
wordList的长度，M 是单词的长度。 - 空间复杂度: O(N * M)，存储转换路径所需空间。
方法一：广度优先搜索（BFS）+ 回溯 图解说明
在方法一中，我们使用广度优先搜索（BFS）和回溯的组合来解决单词接龙 II 问题。这种方法的核心在于逐层扩展当前单词，直到找到目标单词 endWord。图解的详细步骤如下：
- 初始化：
- 创建一个字典
layer来存储每一层的单词及其对应的路径。初始时，layer包含beginWord和它自身构成的路径（["hit"]）。
- 广度优先搜索：
- 遍历当前层的每个单词，尝试改变单词中的每一个字符，用 26 个字母替换，生成新的单词。
- 检查每个新生成的单词是否在
wordList中。如果在，将其加入到下一层的搜索中，并记录路径。 - 重要的是，一旦一个单词被用于构建路径，它就会从
wordList中移除，这避免了重复访问并减少了搜索空间。
- 路径记录：
- 对于每个有效的转换单词，我们更新
newlayer字典，将新单词的路径扩展为从上一层单词衍生出的所有可能路径。 - 例如，从 “hit” 到 “hot”，如果 “hot” 能转换为 “dot” 和 “lot”，则路径更新为从 “hit” 到 “hot” 再到这些单词的路径。
- 检查终点：
- 在每层搜索结束时，检查
endWord是否已经出现在当前层的路径中。如果出现，就意味着找到了最短路径，函数返回当前层对应的endWord的所有路径。
- 循环继续：
- 更新
layer为newlayer，进行下一轮层的搜索，直到找到endWord或者没有新单词可以搜索。
示意图
考虑 beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"] 的情况：
Layer 0: hit | Layer 1: hot / \ Layer 2:dot lot / \ Layer 3:dog log \ / Layer 4: cog
在这个示意图中，广度优先搜索首先找到与 “hit” 一个字母不同的所有单词（即 “hot”），然后再从 “hot” 扩展到 “dot” 和 “lot”，以此类推，直到到达 “cog”。每一步都保证是最短的可能路径，因为我们是逐层扩展的。
方法二：双向广度优先搜索（Bi-directional BFS）
解题步骤
- 从
beginWord和endWord同时开始搜索，每次扩展较小的层。 - 当两个搜索方向在中间某处相遇时，使用所有累积的路径构建最终路径。
Python 示例
def findLadders(beginWord, endWord, wordList): if endWord not in wordList: return [] tree, words, n = defaultdict(set), set(wordList), len(beginWord) if beginWord in words: words.remove(beginWord) found, q, nq = False, {beginWord}, set() while q and not found: words -= set(q) for x in q: for y in [x[:i] + c + x[i + 1:] for i in range(n) for c in 'abcdefghijklmnopqrstuvwxyz']: if y in words: if y == endWord: found = True else: nq.add(y) tree[x].add(y) q, nq = nq, set() def bt(x): return [[x]] if x == endWord else [[x] + rest for y in tree[x] for rest in bt(y)] return bt(beginWord) # Example usage beginWord = "hit" endWord = "cog" wordList = ["hot","dot","dog","lot","log","cog"] print(findLadders(beginWord, endWord, wordList))
算法分析
- 时间复杂度: O(N * M^2)，类似于单向 BFS。
- 空间复杂度: O(N * M)，需要存储中间状态和构建路径。
算法图解与说明
双向广度优先搜索可以更快地找到路径因为它从两端同时搜索，减少了搜索的广度。
这两种方法都可以有效地找出所有最短的从 beginWord 到 endWord 的路径，第二种方法通常更快，尤其是在大数据集上。
🌹🌹如果觉得这篇文对你有帮助的话，记得一键三连关注、赞👍🏻、收藏是对作者最大的鼓励，非常感谢 ❥(^_-)
❤️❤️作者知识有限，如有错误，请各位大佬评论区批评指正，不胜感激❥(^_-)
欢迎关注微信公众号 数据分析螺丝钉
