126.单词接龙Ⅱ python

题目

题目描述

按字典 wordList 完成从单词 beginWord 到单词 endWord 转化，一个表示此过程的 转换序列 是形式上像 beginWord -> s1 -> s2 -> … -> sk 这样的单词序列，并满足：

每对相邻的单词之间仅有单个字母不同。
转换过程中的每个单词 si（1 <= i <= k）必须是字典 wordList 中的单词。注意，beginWord 不必是字典 wordList 中的单词。
sk == endWord
给你两个单词 beginWord 和 endWord ，以及一个字典 wordList 。请你找出并返回所有从 beginWord 到 endWord 的 最短转换序列 ，如果不存在这样的转换序列，返回一个空列表。每个序列都应该以单词列表 [beginWord, s1, s2, …, sk] 的形式返回。

示例 1：

输入：beginWord = “hit”, endWord = “cog”, wordList = [“hot”,“dot”,“dog”,“lot”,“log”,“cog”]
输出：[[“hit”,“hot”,“dot”,“dog”,“cog”],[“hit”,“hot”,“lot”,“log”,“cog”]]
解释：存在 2 种最短的转换序列：
“hit” -> “hot” -> “dot” -> “dog” -> “cog”
“hit” -> “hot” -> “lot” -> “log” -> “cog”

示例 2：

输入：beginWord = “hit”, endWord = “cog”, wordList = [“hot”,“dot”,“dog”,“lot”,“log”]
输出：[]
解释：endWord “cog” 不在字典 wordList 中，所以不存在符合要求的转换序列。

提示：

1 <= beginWord.length <= 5
endWord.length == beginWord.length
1 <= wordList.length <= 500
wordList[i].length == beginWord.length
beginWord、endWord 和 wordList[i] 由小写英文字母组成
beginWord != endWord
wordList 中的所有单词 互不相同

题解

这个问题可以通过广度优先搜索（BFS）来解决，因为我们需要找到从 beginWord 到 endWord 的最短路径。为了有效地找到所有可能的最短转换序列，我们可以在BFS过程中构建一个图，并在到达 endWord 时回溯这个图以找到所有的路径。

解决方案步骤

1. 检查边界条件：首先检查 wordList 中是否包含 endWord。如果不包含，则直接返回空列表，因为无法完成转换。
2. 构建图：使用 BFS 构建一个图，其中每个节点代表一个单词，边连接那些只有一个字符不同的单词。
3. 记录父节点：在 BFS 过程中，记录每个单词的父节点，以便之后可以回溯找到所有最短路径。
4. 回溯寻找所有路径：一旦找到了 endWord，使用记录的父节点信息进行回溯，找出所有从 beginWord 到 endWord 的最短路径。

Python 实现

下面是具体的实现代码：

from collections import defaultdict, deque

def findLadders(beginWord, endWord, wordList):
    # 将 wordList 转换为集合以便快速查找
    wordSet = set(wordList)
    
    if endWord not in wordSet:
        return []
    
    # 如果 beginWord 不在 wordSet 中，添加它
    if beginWord not in wordSet:
        wordSet.add(beginWord)
    
    # 构建通用状态的字典
    all_combo_dict = defaultdict(list)
    for word in wordSet:
        for i in range(len(beginWord)):
            all_combo_dict[word[:i] + "*" + word[i+1:]].append(word)
    
    # BFS 遍历
    queue = deque([(beginWord, [beginWord])])
    visited = set([beginWord])
    found = False
    parents = defaultdict(set)
    
    while queue and not found:
        level_size = len(queue)
        current_visited = set()
        for _ in range(level_size):
            current_word, path = queue.popleft()
            for i in range(len(current_word)):
                intermediate_word = current_word[:i] + "*" + current_word[i+1:]
                for word in all_combo_dict[intermediate_word]:
                    if word == endWord:
                        found = True
                    if word not in visited:
                        if word not in current_visited:
                            queue.append((word, path + [word]))
                            current_visited.add(word)
                        parents[word].add(current_word)
        visited.update(current_visited)
    
    # 回溯找到所有路径
    def backtrack(word, path):
        if word == beginWord:
            result.append(path[::-1])
        else:
            for parent in parents[word]:
                backtrack(parent, path + [parent])
    
    result = []
    if found:
        backtrack(endWord, [endWord])
    
    return result

解释

• 构建通用状态的字典：通过将每个单词中的每个字符替换为通配符 * 来创建一个通用状态字典。例如，“hot” 可以变成 “ot”，“ht”，“ho*”。这有助于快速找到只相差一个字符的单词。

• BFS 遍历：使用队列进行广度优先搜索，同时维护一个 visited 集合来避免重复访问同一个单词。当找到 endWord 时停止遍历。

• 记录父节点：在 BFS 过程中，记录每个单词的所有父节点，以便后续回溯时能够重建路径。

• 回溯寻找所有路径：一旦找到 endWord，使用递归回溯的方法从 endWord 开始追溯到 beginWord，从而生成所有可能的最短路径。

这种方法确保了我们能够找到所有最短路径，并且效率上也较为合理，适合处理题目给定的输入规模。

提交结果