❤️❤️❤️ 欢迎来到我的博客。希望您能在这里找到既有价值又有趣的内容，和我一起探索、学习和成长。欢迎评论区畅所欲言、享受知识的乐趣！
- 推荐：数据分析螺丝钉的首页 格物致知 终身学习 期待您的关注
- 导航：
- LeetCode解锁1000题: 打怪升级之旅：每题都包括3-5种算法，以及详细的代码实现，刷题面试跳槽必备
- 漫画版算法详解：通过漫画的形式和动态GIF图片把复杂的算法每一步进行详细可视解读，看一遍就掌握
- python源码解读：解读python的源代码与调用关系，快速提升代码质量
- python数据分析可视化：企业实战案例：企业级数据分析案例与可视化，提升数据分析思维和可视化能力
- 程序员必备的数学知识与应用：全面详细的介绍了工程师都必备的数学知识
期待与您一起探索技术、持续学习、一步步打怪升级 欢迎订阅本专栏❤️❤️
题目描述
给定两个单词（beginWord 和 endWord）和一个字典 wordList，找出从 beginWord 到 endWord 的最短转换序列的长度。转换需遵循如下规则：
- 每次只能改变一个字母。
- 转换过程中的中间单词必须在字典
wordList中。
说明：
- 如果不存在这样的转换序列，返回 0。
- 所有单词具有相同的长度。
- 所有单词只包含小写字母。
- 字典
wordList是非空的，且不包含重复的单词。 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" 不在字典 wordList 中，因此无转换可能。
方法一：广度优先搜索（BFS）
解题步骤
- 将
wordList转换为集合wordSet，以便快速查找。 - 使用队列实现广度优先搜索。队列中的每个元素是一个元组，包括当前单词和到达该单词的转换次数。
- 对于队列中的每个单词，生成所有可能的单词变换，并检查是否在
wordSet中。如果在，加入队列继续搜索。 - 如果找到
endWord，则当前转换次数即为答案。 - 如果队列耗尽还没有找到
endWord，则表示无法从beginWord转换到endWord。
Python 示例
from collections import deque def ladderLength(beginWord, endWord, wordList): wordSet = set(wordList) # 快速查找 if endWord not in wordSet: return 0 queue = deque([(beginWord, 1)]) # (当前单词, 步数) while queue: current_word, level = queue.popleft() if current_word == endWord: return level # 生成所有单个字符变换的可能单词 for i in range(len(current_word)): for c in 'abcdefghijklmnopqrstuvwxyz': next_word = current_word[:i] + c + current_word[i+1:] if next_word in wordSet: wordSet.remove(next_word) # 移除已访问过的单词防止循环访问 queue.append((next_word, level + 1)) return 0 # 如果没有找到有效的转换路径 # Example usage beginWord = "hit" endWord = "cog" wordList = ["hot","dot","dog","lot","log","cog"] print(ladderLength(beginWord, endWord, wordList)) # Output: 5
算法分析
- 时间复杂度：O(N * M^2)，其中 N 是
wordList的长度，M 是单词的长度。对每个单词，可能的变换有 M*26 种，且检查一个变换是否在wordList中平均需要 O(1) 时间。 - 空间复杂度：O(N)，存储
wordSet及队列中的元素所需的空间。
算法图解与说明
考虑 beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"] 示意的搜索树如下： hit / hot / \ dot lot / \ dog log / cog 广度优先搜索首先访问 "hit" 的所有单字母变换，发现 "hot" 在列表中，然后继续探索 "hot" 的变换 "dot" 和 "lot"，依此类推，直到找到 "cog"。
这种方法确保了找到的第一个解是最短的路径，因为广度优先搜索会层层递进地探索所有可能的路径，直到找到目标单词。
方法二：双向广度优先搜索（Bi-directional BFS）
双向广度优先搜索是优化单向 BFS 的一种常用策略，特别适用于在较大空间中找到两个点之间的最短路径问题。这种方法从两个方向同时进行搜索——一个从 beginWord 开始，另一个从 endWord 开始，并在中间某处相遇，从而显著减少搜索空间和时间。
解题步骤
- 首先检查
endWord是否在wordList中，如果不在，则无法转换，返回 0。 - 使用两个集合
beginSet和endSet分别存储从开始和结束词汇扩展的单词，以便从两端进行搜索。 - 使用
visited集合跟踪已访问的单词以避免重复处理。 - 循环执行以下步骤，直到
beginSet或endSet为空：
- 选择较小的集合进行扩展（这样做可以减少每一步需要处理的单词数量）。
- 为当前集合中的每个单词生成所有可能的单字母变换。
- 如果变换后的单词在对方集合中，说明找到了连接路径，返回当前路径长度。
- 如果变换后的单词在
wordList中且未被访问过，将其加入临时集合并标记为已访问。 - 更新当前扩展集合为临时集合。
- 如果两个集合都被耗尽还没找到路径，则返回 0。
Python 示例
def ladderLength(beginWord, endWord, wordList): if endWord not in wordList: return 0 wordSet = set(wordList) beginSet, endSet = {beginWord}, {endWord} visited = set() step = 1 while beginSet and endSet: if len(beginSet) > len(endSet): beginSet, endSet = endSet, beginSet temp = set() for word in beginSet: for i in range(len(word)): for c in 'abcdefghijklmnopqrstuvwxyz': next_word = word[:i] + c + word[i+1:] if next_word in endSet: return step + 1 if next_word in wordSet and next_word not in visited: temp.add(next_word) visited.add(next_word) beginSet = temp step += 1 return 0 # Example usage beginWord = "hit" endWord = "cog" wordList = ["hot","dot","dog","lot","log","cog"] print(ladderLength(beginWord, endWord, wordList)) # Output: 5
算法分析
- 时间复杂度：O(N * M^2)，N 是
wordList的长度，M 是单词的长度。尽管仍然需要检查单词的所有单字母变换，但双向搜索通常比单向 BFS 快得多。 - 空间复杂度：O(N)，主要是
wordSet和visited的存储空间。
算法图解与说明
考虑 beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"] 双向搜索树可能如下： 从 'hit' 开始: hit -> hot -> dot -> dog ↗ 从 'cog' 开始: cog -> dog 在 'dog' 处两边搜索相遇，总步数为 5。
双向 BFS 有效地缩短了搜索路径，通过在中间某点相遇来连接从开始和结束词汇扩展的路径，从而更快地找到最短路径。
🌹🌹如果觉得这篇文对你有帮助的话，记得一键三连关注、赞👍🏻、收藏是对作者最大的鼓励，非常感谢 ❥(^_-)
❤️❤️作者知识有限，如有错误，请各位大佬评论区批评指正，不胜感激❥(^_-)
欢迎关注微信公众号 数据分析螺丝钉
![[leetcode/lintcode 题解] 阿里算法面试题：单词接龙 II](https://ucc.alicdn.com/pic/developer-ecology/2b9728f1e53f46669b779a4d6fb948b7.png?x-oss-process=image/resize,h_160,m_lfit)