怎么把自己做的网站登录到网上,网站设计公司 无锡,网站下载不了视频,营销推广策略❤️❤️❤️ 欢迎来到我的博客。希望您能在这里找到既有价值又有趣的内容#xff0c;和我一起探索、学习和成长。欢迎评论区畅所欲言、享受知识的乐趣#xff01; 推荐#xff1a;数据分析螺丝钉的首页 格物致知 终身学习 期待您的关注 导航#xff1a; LeetCode解锁100… ❤️❤️❤️ 欢迎来到我的博客。希望您能在这里找到既有价值又有趣的内容和我一起探索、学习和成长。欢迎评论区畅所欲言、享受知识的乐趣 推荐数据分析螺丝钉的首页 格物致知 终身学习 期待您的关注 导航 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, dequedef 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[i1:]if newword in wordList:newlayer[newword] [j [newword] for j in layer[word]]wordList - set(newlayer.keys())layer newlayerreturn []# 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 Trueelse: 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 的路径第二种方法通常更快尤其是在大数据集上。 如果觉得这篇文对你有帮助的话记得一键三连关注、赞、收藏是对作者最大的鼓励非常感谢 ❥(^_-) ❤️❤️作者知识有限如有错误请各位大佬评论区批评指正不胜感激❥(^_-)
