126. Word Ladder II

Title

给定两个单词（beginWord 和 endWord）和一个字典 wordList，找出所有从 beginWord 到 endWord 的最短转换序列。转换需遵循如下规则：

每次转换只能改变一个字母。
转换过程中的中间单词必须是字典中的单词。

说明:

如果不存在这样的转换序列，返回一个空列表。
所有单词具有相同的长度。
所有单词只由小写字母组成。
字典中不存在重复的单词。
你可以假设 beginWord 和 endWord 是非空的，且二者不相同。

示例 1:

输入:

beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]

输出:

[["hit","hot","dot","dog","cog"],["hit","hot","lot","log","cog"] ]

示例 2:

输入:

beginWord = "hit" endWord = "cog" wordList = ["hot","dot","dog","lot","log"]

输出:

[]

解释: endWord “cog” 不在字典中，所以不存在符合要求的转换序列。

Solve

将所有单词构建桶，便于查找邻接词。构建桶的方式是依次将一个词的各个字母挖空，用字典进行保存

广度优先搜索进行遍历，这里构建三个数据结构：

• beFound：用于标记首次遍历的词，同时记录首次遍历的深度
• preWords：用一个默认列表字典记录到达该节点的前溯词列表，需注意对于每个可能搜索到该词的路径，只要深度不超过已有路径，都应加入前溯词列表
• toSeen：用一个双端队列存储待遍历词及当前深度。

如果搜索到了目标节点endWord，则依次往前递归输出解：每个解的头节点若包含多个前溯词，则解相应增加。利用python列表嵌套推导式实现。

Code

class Solution:def findLadders(self, beginWord: str, endWord: str, wordList: List[str]) -> List[List[str]]:length = len(beginWord)wordList.append(beginWord)# 构建具有邻接关系的桶buckets = defaultdict(list)for word in wordList:for i in range(length):match = word[:i] + '_' + word[i + 1:]buckets[match].append(word)print(buckets)# BFS遍历preWords = defaultdict(list) # 前溯词列表toSeen = deque([(beginWord, 1)]) # 待遍历词及深度列表beFound = {beginWord: 1} # 已探测词词列表while toSeen:curWord, level = toSeen.popleft()for i in range(len(beginWord)):match = curWord[:i] + '_' + curWord[i + 1:]for word in buckets[match]:if word not in beFound:beFound[word] = level + 1toSeen.append((word, level + 1))if beFound[word] == level + 1: # 当前深度等于该词首次遍历深度，则仍应加入前溯词列表preWords[word].append(curWord)if endWord in beFound and level + 1 > beFound[endWord]: # 已搜索到目标词，且完成当前层遍历break# 列表推导式输出结果if endWord in beFound:res = [[endWord]]while res[0][0] != beginWord:res = [[word] + r for r in res for word in preWords[r[0]]]return reselse:return []

总结

以上是生活随笔为你收集整理的126. Word Ladder II的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。