算法面试：如何用双向 BFS 解单词接龙？

题干与适用场景

给定 beginWord、endWord 和 wordList，求最短转换序列的长度。相邻两个单词必须恰好有一个 位置不同；除 beginWord 外的每个单词都必须出现在词典中，endWord 也不例外。返回值计算 单词数，而不是修改次数。

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

一条最短序列：
hit -> hot -> dot -> dog -> cog

返回：5

采用标准约束：beginWord 与 endWord 不同；全部单词只含小写英文字母；词典单词长度都为 L、互不重复；词典最多有 N = 5,000 个单词。endWord 不在词典中或不可达时返回 0。

这道题把图藏在字符串里。每个合法单词是一个顶点；两个单词恰好相差一个字母时，存在一条无向、 单位代价的边。因此，题目要求在无权图中寻找单源单目标最短路。2026 年公开的图算法面试材料仍把 单词接龙列为 BFS 转换题，2026 年 6 月的一份公开面试记录还讨论了更难的 Word Ladder II。 这些材料只能证明本题当前仍有准备价值，不能证明面试频率或公司归属，所以本文不作这两类声称。

面试官考察点

第一项信号是能否识别隐式图。逐对比较所有词可以建出正确的图，但要做 O(N²) 次比较，每次 花 O(L)。更强的回答只生成当前单词可能存在的邻居：逐个位置替换成其余 25 个字母，再通过 哈希集合判断候选词是否在词典中。

第二项信号是最短路推导。每次转换的代价都是一，所以 BFS 按距离非递减顺序搜索。DFS 最终可能 找到路径，却不能保证第一条路径最短；Dijkstra 对单位权重也正确，但优先队列没有带来额外信息。

第三项信号是访问标记的时机。单词进入前沿时就必须移出未访问集合，不能等到之后展开时才删除。 延迟标记会让多个父节点重复加入同一个单词，增加时间和内存。双向 BFS 生成候选词后，应先检查 它是否位于另一侧当前前沿，再检查未访问集合。

第四项信号是能否证明优化没有破坏正确性。双向 BFS 在两个端点各维护一个完整层前沿，每次展开 较小的前沿。在近似树形、有效分支数为 b、答案边数为 d 时，实际探索量常从接近 b^d 降到两次约 b^(d/2) 的搜索。但它没有改善最坏渐进上界：对抗词典仍可能让算法检查几乎全部 单词。

最后还要准确核算字符串成本。每个展开的单词最多尝试 25L 个变体。在 Python 中，创建候选 字符串要复制 O(L) 个字符，所以固定 26 字母表下，这份实现的期望时间为 O(NL²)，字符 存储为 O(NL)。直接写成 O(NL) 等于错误地把字符串构造当成常数操作。

回答前需要澄清的问题

• 返回值究竟计算什么？ 本题同时计算两个端点，因此一次直接合法转换返回 2；若接口要求

边数，结果应少一。

• endWord 必须在词典中吗？ 必须。不在时搜索前直接返回 0。允许目标不在词典中的变体

会改变这条提前结束规则。

• 单词长度和字母表是否固定？ 是，长度为 L，只含小写英文字母。Unicode、不同长度或更大

字母表会改变邻居生成方式和成本。

• 词典元素是否唯一？ 是。仍要转换为集合以获得期望 O(1) 的查找和删除。即使允许重复，

重复字符串也不应形成多个顶点。

• 要返回长度、一条路径还是全部最短路径？ 基础题只要长度。返回一条路径需要双向父指针；

返回全部最短路径要保留同一 BFS 层的全部父节点，不能原样照搬立即删除规则。

• 词典只查询一次还是会服务很多查询？ 单次查询适合按需替换字母，不必建完整索引；稳定词典

上的大量查询可能值得复用通配模式索引。

• beginWord 可能已经在词典中吗？ 可以。它仍是一个顶点，初始化时应从未访问集合删除。

30 秒回答框架

“我会把每个单词看成顶点，恰好相差一个位置的两个词之间连边。每条边代表一次转换，所以这是无权 最短路。我从 beginWord 和 endWord 同时做 BFS，每轮展开较小的完整层前沿。对前沿中的每个 单词，生成最多 25L 个单字母变体并在哈希集合中查找。如果候选词位于另一侧当前前沿，两段最短 前缀已经连接，返回当前单词计数加一；否则，未访问候选词一加入下一层就立刻从集合删除。 endWord 不在词典中或任一前沿耗尽时返回零。最坏仍会访问 N 个单词；Python 构造每个候选词 需要复制 L 个字符，因此时间是 O(NL²)，字符存储是 O(NL)。我会测试直接转换、不可达、 环、多父节点重复发现和两侧前沿大小悬殊的情况。”

分步骤深入解答

先建立图模型。顶点集合包含全部词典单词和 beginWord。任意两个等长单词的汉明距离为一时连边。 这张图是无向图：hot 能变成 dot，反向也合法；它也是无权图，因为每次合法修改只贡献一条边。

显式建图要逐对比较单词，预处理为 O(N²L)，即使绝大多数单词互不相邻也要支付成本。输入的 字母表提供了更小的候选空间：每个单词最多只有 25L 个不同的单字母变体，集合成员判断再确定 哪些候选是真实顶点。

单向 BFS 已经正确。它维持下面的不变量：

在第 k 层开始时：
  frontier 恰好包含边距离为 k 的已发现单词；
  不存在距离小于 k 的未发现单词；
  所有已离开 unvisited 的单词都已经得到最小距离。

BFS 只从第 k 层生成第 k + 1 层，所以某个单词首次被发现时，路径已经最短。在发现时就从 unvisited 删除它，既保留这项事实，也避免重复进入前沿。

单个目标已知时，可以从两端搜索。front 是起点侧的一个完整距离层，back 是终点侧的一个 完整距离层。sequence_length 等于两个当前前沿深度之和再加一，因为它计算两侧前沿单词，却 还没有算连接它们的边。展开任意一侧的完整层都会让深度和增加一。如果生成的候选词属于另一侧 前沿，连接边使答案成为 sequence_length + 1。

展开较小前沿只改变性能，不改变正确性。交换两个集合只是选择下一步推进哪个合法 BFS 层；两边 依旧分别表示距各自端点的一个确定深度。相交判断必须针对另一侧当前前沿。使用一个全局 unvisited 是安全的：一侧发现单词时会立即占用它。假如之后另一侧的展开边能够跨到已经展开的 旧层，那么旧层当初展开时就会先发现同一个单词，因此两次搜索不会在当前前沿背后悄悄交叉。

ALPHABET = "abcdefghijklmnopqrstuvwxyz"


def ladder_length(
    begin_word: str,
    end_word: str,
    word_list: list[str],
) -> int:
    unvisited = set(word_list)
    if end_word not in unvisited:
        return 0

    front = {begin_word}
    back = {end_word}
    unvisited.discard(begin_word)
    unvisited.remove(end_word)
    sequence_length = 1

    while front and back:
        if len(front) > len(back):
            front, back = back, front

        next_front: set[str] = set()

        for word in front:
            for index, original in enumerate(word):
                for letter in ALPHABET:
                    if letter == original:
                        continue

                    candidate = word[:index] + letter + word[index + 1 :]

                    if candidate in back:
                        return sequence_length + 1

                    if candidate in unvisited:
                        unvisited.remove(candidate)
                        next_front.add(candidate)

        front = next_front
        sequence_length += 1

    return 0

样例的前沿层次如下：

第三轮会改为展开更小的 cog 侧。第四轮中，dot 与 dog 或 lot 与 log 相连，于是返回 5。集合迭代顺序可能选择另一条最短相交边，但长度不变。

令 N 为词典规模，L 为词长。每个单词最多进入前沿一次；若被展开，就尝试 25L 个候选。 哈希查找期望为 O(1)，但 Python 的切片和拼接每次花 O(L)，所以固定字母表下最坏期望时间 为 O(NL²)。集合最多保存 O(N) 个引用，其中字符串包含 O(NL) 个字符；临时候选词一次 额外占 O(L)。即使用可变字符缓冲，物化或哈希候选词仍要查看 L 个字符，严谨上界不变。

主要替代方案是通配模式索引。把 hot 映射到 *ot、h*t、ho* 等桶。大量查询可以复用 索引，也不用尝试词典从未出现的字母。在 Python 中，为 N 个单词建立 L 个模式同样包含 O(NL²) 的字符工作，并保留 O(NL) 个桶条目。BFS 使用过某个模式后要清空对应桶或记录已 处理，否则很多单词会反复扫描同一个大桶，重新产生平方级工作。当前约束下只有一次查询，按需 变异加集合更容易实现和证明。

测试要覆盖可执行契约，不只跑样例：

cases = [
    (
        "hit",
        "cog",
        ["hot", "dot", "dog", "lot", "log", "cog"],
        5,
    ),
    ("hit", "cog", ["hot", "dot", "dog", "lot", "log"], 0),
    ("a", "c", ["a", "b", "c"], 2),
    ("red", "tax", ["ted", "tex", "red", "tax", "tad", "den", "rex", "pee"], 4),
    ("aaa", "bbb", ["aab", "abb", "bbb", "aba", "baa"], 4),
]

for begin_word, end_word, words, expected in cases:
    actual = ladder_length(begin_word, end_word, words)
    assert actual == expected, (begin_word, end_word, actual, expected)

属性测试可以随机生成小词典，逐对比较建立显式图，用普通 BFS 作为可信 oracle，再与优化函数 比较。还应确认输入列表不变，覆盖一侧前沿增长远快于另一侧的词典，并验证经多个父节点可达的 单词只会展开一次。

高质量示范回答

“这些单词构成一张隐式无向图。合法单词是顶点，汉明距离为一时连边。每条边代价都是一，所以 BFS 能求出最少转换次数。本题返回单词数，因此 hit -> hot 的长度是二。

我先把词典放进集合；如果 endWord 不存在，直接返回零。随后在两个端点分别维护一个前沿，并 维护一份两侧都尚未发现的单词集合。每轮展开较小的完整前沿。对每个单词的每个位置，尝试其余 25 个小写字母。先判断候选词是否在另一侧当前前沿中；如果命中，两段 BFS 最短前缀已经连接， 返回累计单词数加一。否则，候选词若尚未访问，就立即删除并加入下一层。

不变量是：两个前沿分别是距各自端点的一个精确距离层；任何已删除单词都已经取得发现侧的最小 距离。展开较小一侧不会破坏层次。第一次前沿相连一定最短，因为任何更短路径都会在更早、深度和 更小的两层之间产生连接。发现时删除可以阻止重复加入。

最多展开 N 个单词。每个单词生成 25L 个变体，Python 构造每个候选词花 O(L)，所以我会 写期望时间 O(NL²)、字符存储 O(NL)。双向搜索通常减少访问状态，但最坏上界不变。若稳定 词典要服务大量查询，我会考虑复用通配索引；单次查询用字符替换更简单。验证包括官方样例、目标 缺失、直接转换、多条最短路径、环，以及与随机显式图 oracle 对比。”

常见错误

• 用 DFS 并返回第一条路径 → DFS 不按转换次数访问路径 → 所有边权为一时使用 BFS。
• 逐对比较所有词典单词 → 建图成本达到 O(N²L) → **每个展开单词只生成最多 25L 个

候选邻居。**

• 出队时才标记访问 → 多个父节点可能重复加入同一个词 → **加入前沿时就从 unvisited

删除。**

• 先检查 unvisited，后检查另一侧前沿 → 相交词已经被另一侧删除 → **先检查另一侧当前

前沿。**

• 固定展开名为 front 的一侧 → 一侧可能爆炸增长、另一侧仍很小 → **交换并展开较小的完整

层前沿。**

• 混淆边数和单词数 → 样例返回四而不是五 → 计数从一开始，相交时加入连接单词。
• 声称双向 BFS 改善最坏复杂度 → 对抗词典仍可能暴露几乎所有单词 → **把分支数收益描述为

常见表现，不作保证。**

• 把 Python 变异成本写成 O(NL) → 每个候选词都会复制或哈希 L 个字符 → **明确字符串

操作模型，这份实现写 O(NL²)。**

• 复用通配桶却不消费 → 同一个大桶被重复扫描 → 每个模式处理后清空或标记。
• 使用全局访问集合，却只展开半层 → 相交顺序和距离计数难以证明 → **每轮推进一个完整前沿

层。**

• 把个人发帖当作已核实的公司真题 → 公开自述不是雇主记录 → **companyName 保持为空，

仅用它证明当前存在公开讨论。**

追问及应对

追问一：如何返回一条实际的最短序列？

为两个方向分别保存父指针。发现候选词时记录产生它的单词。相交后，沿起点侧父指针回到 beginWord 并反转前缀，再沿终点侧父指针走向 endWord。实现会交换前沿变量，所以父指针必须 按“起点方向”和“终点方向”保存，不能假设当前 front 永远来自起点。除词典字符串外，父指针 还需要 O(N) 个引用。

追问二：Word Ladder II 要返回全部最短序列，哪里要改？

每个单词只存一个父节点不够。普通分层 BFS 往往更容易证明：记录在最小层到达同一单词的所有 前驱，并在整层处理完后才从全局词典删除本层新发现的单词。这样允许同层多个父节点，同时阻止 更长路径继续加父节点。首次到达 endWord 后仍要完成当前层，再在前驱 DAG 上回溯。输出数量 可能是指数级，复杂度必须包含全部返回序列的数量和长度。

追问三：什么时候普通单向 BFS 更合适？

词典很小、只知道一个端点、图有方向且反向邻居很难生成，或代码简单性比减少前沿更重要时，使用 单向 BFS。它的不变量更少，父指针重建也直接。这份 Python 表示下，它沿用同一邻居生成器和 O(NL²) 上界。

追问四：什么时候应建立通配模式桶？

大量查询共享稳定词典、字母表很大，或枚举每个字母浪费明显时建立索引。索引要与词典版本绑定； beginWord 不在索引中时，每次查询单独生成其模式；一次搜索内每个桶最多消费一次。代价是 预处理时间、桶内存和词典变化时的失效处理。

追问五：不同字母修改的代价不同时怎么办？

图变为带权图，BFS 层次不再代表最小代价。非负代价使用 Dijkstra，仍按需生成相同的隐式邻居， 但按累计代价选择前沿。若有可采纳启发式可以使用 A*；只有把汉明距离乘以“任意剩余字符修改的 已证明最小代价”时，才能直接保证其可采纳性。

追问六：字母表是 Unicode，或单词长度不同时怎么办？

先定义合法操作。Unicode 码点与用户看到的字素簇并非同一单位；允许插入和删除后还会出现跨长度 边。单纯枚举替换不再覆盖整张图。应按契约选择编辑距离为一的邻居索引、Trie 或按长度和模式 分桶，并把规范化规则纳入相等性与哈希。

追问七：面试中怎样证明双向搜索的停止条件？

给两个当前前沿分别标出到各自端点的深度。算法每轮只推进一个完整深度层。展开前， sequence_length 等于两个前沿深度之和加一。生成边进入另一侧前沿时，这条边组成的路径恰有 sequence_length + 1 个单词。若存在更短路径，它必然包含一条连接深度和更小的两层的边；这 两层已经更早展开并相连，与当前是首次相交矛盾。

追问八：除样例外，怎样验证优化搜索？

对小型随机词典，逐对连接汉明距离为一的单词，运行普通 BFS oracle，再把结果与双向 BFS 比较， 重复数千组。另加运行时不变量：两个前沿都不与 unvisited 相交；单词不会被发现两次；下一层 每个单词都与当前层某个单词只差一个字符。这样得到的是正确性证据，不只是几个手选输出。