单词接龙（LeetCode 127）：Python 中使用通配符模式的 BFS

Word Ladder（LeetCode 127）要求找出从一个单词到另一个单词的最短转换序列长度，每次只能改一个字母，且每一步得到的单词都必须在给定的词表中。每步代价相同的最短路径，自然要用广度优先搜索。让它跑得快的关键技巧，是按 h*t 这样的通配符模式给单词分组，这样就不用两两比较所有单词。

题目

给定 beginWord、endWord 和一个单词列表，返回从 beginWord 到 endWord 的最短转换序列中的单词数量，两端都算在内。每一步只改一个字母，且转换后的单词必须在列表中。如果不存在这样的序列，返回 0。

为什么用广度优先搜索

把每个单词看作一个节点，两个只差一个字母的单词之间连一条边。每条边的代价都是一步，所以最短序列就是无权图中的最短路径，而广度优先搜索第一次到达终点单词时找到的就是它。

暴力建边

两两比较单词、判断是否只差一个字母，对于 N 个长度为 L 的单词，代价是 O(N 的平方乘以 L)。单词上千时就太慢了。更好的做法是：用模式生成邻居。

思路：通配符模式

依次把每个字母替换成 *。hot 就变成 *ot、h*t 和 ho*。两个单词是邻居，当且仅当它们共享同一个模式。先建立从模式到符合该模式的单词的映射，再用它来搜索。

from collections import deque, defaultdict

def ladder_length(begin_word, end_word, word_list):
    words = set(word_list)
    if end_word not in words:
        return 0
    patterns = defaultdict(list)
    for w in words | {begin_word}:
        for i in range(len(w)):
            patterns[w[:i] + "*" + w[i + 1:]].append(w)
    queue = deque([(begin_word, 1)])
    seen = {begin_word}
    while queue:
        word, steps = queue.popleft()
        if word == end_word:
            return steps
        for i in range(len(word)):
            key = word[:i] + "*" + word[i + 1:]
            for nxt in patterns[key]:
                if nxt not in seen:
                    seen.add(nxt)
                    queue.append((nxt, steps + 1))
            patterns[key] = []
    return 0

有两个细节很重要。起始单词即使不在列表中，也要加入模式映射，因为你是从它出发的。另外，某个模式的单词被访问过后，用 patterns[key] = [] 把它清空，这样共享该模式的其它单词就不会再重复扫描同一组。这样总工作量与模式数量成线性关系。

复杂度

建立模式需要 O(N 乘以 L)，而每个模式字符串的构建代价是 O(L)，所以总共约为 O(N 乘以 L 的平方)。搜索过程中每个单词访问一次、每个模式组访问一次，复杂度上界相同。空间是 O(N 乘以 L 的平方)，用于存储模式映射，因为每个单词都会存在 L 个长度为 L 的键下。

更快：双向搜索

从起始单词和终点单词各跑一次搜索，每次总是扩展较小的那一侧边界。两边在中间相遇，所以每侧只需搜索一半深度。如果面试官问怎么加速，可以提一下，不过它的代码量比大多数面试期望你写的要多。

常见错误

• 返回的是改动次数而不是单词数量。序列包含 beginWord，所以例子答案是 5，不是 4。
• 搜索前没有检查 endWord 是否在列表中。
• 用两两比较来建邻居，结果超时。
• 让搜索重复访问单词，导致死循环或变慢。
• 用 DFS，它能找到一条路径，但不是最短的。

要测试的边界情况

面试中怎么讲

1. 把它重新表述为图的问题，并说明为什么广度优先搜索能找到最短路径。
2. 指出两两比较太慢，引出通配符模式。
3. 写出模式映射、队列和已访问集合。
4. 说明你数的是单词数而不是编辑次数，并用第一个例子演示。
5. 给出复杂度，并提到双向搜索。

发布前，我用上面的代码和普通的逐对广度优先搜索在 20000 个随机小词表上做了对比测试，另外还测了表格里的两个例子。练习时做这种快速随机验证是个好习惯。

相关练习

复杂度术语见我们的 Big O 速查表，接下来练什么见 LeetCode Blind 75 清单，怎么练习见编程面试助手指南。

写代码时把思路讲出来。面试记录能看出你在动手前有没有说出关键观察。在任何实时评估中，都要遵守雇主关于 AI 工具的规定。