题目描述

给定两个单词(beginWordendWord)和一个字典 wordList,找出所有从 beginWordendWord 的最短转换序列的转换过程,转换需遵循如下规则:

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

说明:

  • 如果不存在这样的转换序列,返回一个空列表。
  • 所有单词具有相同的长度。
  • 所有单词只包含小写字母。
  • 字典 wordList 是非空的,且不包含重复的单词。
  • beginWordendWord 是非空的,且不相同。

示例:

输入:

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

输出:

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

方法一:广度优先搜索(BFS)+ 回溯

解题步骤

  1. 使用 BFS 确定最短路径长度并记录每个单词的所有可能前驱词。
  2. endWord 开始,使用回溯法根据前驱词列表构造所有有效路径。

Python 示例

from collections import defaultdict, deque

def 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[i+1:]
                    if newword in wordList:
                        newlayer[newword] += [j + [newword] for j in layer[word]]
        
        wordList -= set(newlayer.keys())
        layer = newlayer
    
    return []

# 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。图解的详细步骤如下:

  1. 初始化

    • 创建一个字典 layer 来存储每一层的单词及其对应的路径。初始时,layer 包含 beginWord 和它自身构成的路径(["hit"])。
  2. 广度优先搜索

    • 遍历当前层的每个单词,尝试改变单词中的每一个字符,用 26 个字母替换,生成新的单词。
    • 检查每个新生成的单词是否在 wordList 中。如果在,将其加入到下一层的搜索中,并记录路径。
    • 重要的是,一旦一个单词被用于构建路径,它就会从 wordList 中移除,这避免了重复访问并减少了搜索空间。
  3. 路径记录

    • 对于每个有效的转换单词,我们更新 newlayer 字典,将新单词的路径扩展为从上一层单词衍生出的所有可能路径。
    • 例如,从 “hit” 到 “hot”,如果 “hot” 能转换为 “dot” 和 “lot”,则路径更新为从 “hit” 到 “hot” 再到这些单词的路径。
  4. 检查终点

    • 在每层搜索结束时,检查 endWord 是否已经出现在当前层的路径中。如果出现,就意味着找到了最短路径,函数返回当前层对应的 endWord 的所有路径。
  5. 循环继续

    • 更新 layernewlayer,进行下一轮层的搜索,直到找到 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)

解题步骤

  1. beginWordendWord 同时开始搜索,每次扩展较小的层。
  2. 当两个搜索方向在中间某处相遇时,使用所有累积的路径构建最终路径。

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 = True
                    else: 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),需要存储中间状态和构建路径。

算法图解与说明

双向广度优先搜索可以更快地找到路径因为它从两端同时搜索,减少了搜索的广度。

这两种方法都可以有效地找出所有最短的从 beginWordendWord 的路径,第二种方法通常更快,尤其是在大数据集上。

05-15 09:42