LeetCode 126. 单词接龙 II

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

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

说明：

• 如果不存在这样的转换序列，返回空列表
• 所有单词具有相同的长度
• 所有单词只由小写字母组成
• 字典中不存在重复的单词
• beginWord 和 endWord 非空，且不相同

解题过程：

步骤1：问题分析
这是一个典型的图搜索问题：

• 每个单词可以看作图中的一个节点
• 如果两个单词只有一个字母不同，它们之间有一条边
• 需要找到所有从起点到终点的最短路径

步骤2：构建图结构
为了高效查找相邻节点，我们使用"通配符"方法：

• 对每个单词，生成所有可能的变化模式
• 比如"hot"可以生成"ot"、"ht"、"ho*"
• 拥有相同模式的单词互为相邻节点

from collections import defaultdict

def build_graph(wordList):
    graph = defaultdict(list)
    for word in wordList:
        for i in range(len(word)):
            pattern = word[:i] + '*' + word[i+1:]
            graph[pattern].append(word)
    return graph

步骤3：双向BFS寻找最短路径长度
为了优化搜索效率，我们使用双向BFS：

• 从起点和终点同时开始搜索
• 当两个方向的搜索相遇时，找到最短路径

def bidirectional_bfs(beginWord, endWord, graph):
    if endWord not in wordSet:
        return 0
    
    # 初始化两个方向的队列和访问集合
    begin_queue = deque([beginWord])
    end_queue = deque([endWord])
    begin_visited = {beginWord: 1}
    end_visited = {endWord: 1}
    
    while begin_queue and end_queue:
        # 从较小的一端开始扩展
        if len(begin_queue) <= len(end_queue):
            level = expand_level(begin_queue, begin_visited, end_visited, graph)
        else:
            level = expand_level(end_queue, end_visited, begin_visited, graph)
        
        if level > 0:
            return level
    
    return 0

def expand_level(queue, visited, other_visited, graph):
    level_size = len(queue)
    for _ in range(level_size):
        word = queue.popleft()
        current_level = visited[word]
        
        # 生成所有相邻单词
        for i in range(len(word)):
            pattern = word[:i] + '*' + word[i+1:]
            for neighbor in graph[pattern]:
                if neighbor in other_visited:
                    return current_level + other_visited[neighbor]
                if neighbor not in visited:
                    visited[neighbor] = current_level + 1
                    queue.append(neighbor)
    return 0

步骤4：DFS回溯构建所有最短路径
知道最短路径长度后，使用DFS回溯构建所有路径：

def dfs_backtrack(word, endWord, path, result, graph, distance, visited):
    if word == endWord:
        result.append(path[:])
        return
    
    if len(path) >= distance:  # 超过最短路径长度，剪枝
        return
    
    for i in range(len(word)):
        pattern = word[:i] + '*' + word[i+1:]
        for neighbor in graph[pattern]:
            if neighbor not in visited and neighbor in wordSet:
                visited.add(neighbor)
                path.append(neighbor)
                dfs_backtrack(neighbor, endWord, path, result, graph, distance, visited)
                path.pop()
                visited.remove(neighbor)

步骤5：完整算法整合
将上述步骤整合成完整解决方案：

from collections import defaultdict, deque

def findLadders(beginWord, endWord, wordList):
    if endWord not in wordList:
        return []
    
    wordSet = set(wordList)
    wordSet.add(beginWord)
    
    # 构建图
    graph = defaultdict(list)
    for word in wordSet:
        for i in range(len(word)):
            pattern = word[:i] + '*' + word[i+1:]
            graph[pattern].append(word)
    
    # 双向BFS找到最短路径长度
    def bidirectional_bfs():
        if beginWord == endWord:
            return 1
            
        begin_visited = {beginWord: 1}
        end_visited = {endWord: 1}
        begin_queue = deque([beginWord])
        end_queue = deque([endWord])
        
        while begin_queue and end_queue:
            # 总是扩展较小的一端
            if len(begin_queue) <= len(end_queue):
                queue, visited, other_visited = begin_queue, begin_visited, end_visited
            else:
                queue, visited, other_visited = end_queue, end_visited, begin_visited
                
            level_size = len(queue)
            for _ in range(level_size):
                current = queue.popleft()
                current_level = visited[current]
                
                for i in range(len(current)):
                    pattern = current[:i] + '*' + current[i+1:]
                    for neighbor in graph[pattern]:
                        if neighbor in other_visited:
                            return current_level + other_visited[neighbor]
                        if neighbor not in visited:
                            visited[neighbor] = current_level + 1
                            queue.append(neighbor)
            return 0
    
    shortest_length = bidirectional_bfs()
    if shortest_length == 0:
        return []
    
    # DFS回溯构建所有路径
    result = []
    
    def dfs(current, path, visited):
        if len(path) == shortest_length:
            if current == endWord:
                result.append(path[:])
            return
        
        if len(path) > shortest_length:
            return
            
        for i in range(len(current)):
            pattern = current[:i] + '*' + current[i+1:]
            for neighbor in graph[pattern]:
                if neighbor not in visited and neighbor in wordSet:
                    visited.add(neighbor)
                    path.append(neighbor)
                    dfs(neighbor, path, visited)
                    path.pop()
                    visited.remove(neighbor)
    
    dfs(beginWord, [beginWord], set([beginWord]))
    return result

步骤6：复杂度分析

• 时间复杂度：O(N × L²)，其中N是单词数量，L是单词长度
• 空间复杂度：O(N × L) 用于存储图结构和中间结果

这个算法通过双向BFS确定最短路径长度，再通过DFS回溯构建所有最短路径，既保证了找到最优解，又避免了不必要的搜索。