LC127 单词接龙 · 逐题动画 · RuntimeScope

RuntimeScope/算法实验台/56 天打卡/141 题/LC127

题型地图 56天全屏 141题

当前：LC127 · 单词接龙 · 首次出现于 Day 34 · 路径：顶栏「56天打卡」→ 点击 LC 题号 → 逐题动画

← LC125 LC128 →

56 / 141回到 Day 34 卡片 141 题索引

LC127 · 单词接龙 · 工程执行实验室

隐形图上的 BFS 扩散

单词列表是一张隐形无权图：结点 = 单词，边 = 只差一个字母。BFS 按层从 beginWord 扩散，第一次到达 endWord 的层数就是最短序列长度（含起点）。

begin: hit → end: cog

wordList: hot,dot,dog,lot,log,cog

答案: 5（序列长度，非 4 次变化）

核心机制 · 隐形图 + BFS

单词列表是一张隐形无权图：结点=单词，边=只差一个字母；BFS 按层扩散，第一次到达 endWord 的层数就是最短序列长度。

· 结点 = 单词；边 = 只差一个字母（无权，代价 1）。
· BFS 按层扩散，level 从 beginWord 算起 = 序列长度。
· size := len(queue) 冻结当前层；visited 入队时标记。

单词图结构（hit → cog）

hit - hot - dot - dog - cog
       |             |
       lot - log ----

最短路径 hit→hot→dot→dog→cog，5 个单词，返回 5。

不变量

BFS 在无权图上按距离从近到远扩展。queue 中同一层的单词连续排列；每层开始用 size := len(queue) 冻结，只处理本层。visited 在入队时标记，保证每个单词最多入队一次。第一次出队 endWord 时，level 即为最短序列长度。

1/18 · 读题

分镜：

Step 1读题

读题：单词列表如何变成最短变换序列？

beginWord="hit"，endWord="cog"，wordList=[hot,dot,dog,lot,log,cog]。每次只能改一个字母，且中间词必须在 wordList 中。求最短序列长度。

单词列表是一张隐形无权图：结点=单词，边=只差一个字母；BFS 按层扩散，第一次到达 endWord 的层数就是最短序列长度。

为什么

关键不是背 BFS 模板，而是先看见「单词列表 = 一张隐形图」。

状态表 · queue / level / visited

queue

[]

level

—

尚未开始 BFS

visited

∅

answer

—

BFS 队列执行表

BFS 执行表将在逐步播放时填充

单词图 · BFS 层级扩散

Go · ladderLength

1func ladderLength(beginWord, endWord string, wordList []string) int {
2    wordSet := make(map[string]bool)
3    for _, w := range wordList {
4        wordSet[w] = true
5    }
6    if !wordSet[endWord] {
7        return 0
8    }
9    queue := []string{beginWord}
10    visited := map[string]bool{beginWord: true}
11    level := 1
12    for len(queue) > 0 {
13        size := len(queue)
14        for i := 0; i < size; i++ {
15            word := queue[0]
16            queue = queue[1:]
17            if word == endWord {
18                return level
19            }
20            for j := 0; j < len(word); j++ {
21                for c := 'a'; c <= 'z'; c++ {
22                    next := word[:j] + string(c) + word[j+1:]
23                    if !wordSet[next] || visited[next] {
24                        continue
25                    }
26                    visited[next] = true
27                    queue = append(queue, next)
28                }
29            }
30        }
31        level++
32    }
33    return 0
34}

行级解释

L2,3,4

wordSet 用于 O(1) 判断单词是否存在

L6,7

endWord 不在 wordList 时直接返回 0

L8,9,10

queue 初始化为 beginWord，level 从 1 起

L12

size := len(queue) 冻结当前 BFS 层

L14,15

出队队首 word，准备扩展邻居

L16,17

出队时若已是 endWord，返回到达层数

L19,20,21

逐位尝试 a-z 生成 next

L22,23

next 必须在 wordSet 且未 visited

L24,25

入队时标记 visited，避免重复入队

L29

整层处理完才 level++

为什么正确

· 这是一张无权图：每条边代表「改一个字母」，代价相同。
· BFS 按距离从近到远搜索，先处理的层一定更近。
· 第一次到达 endWord 时，路径上的单词数（含起点）就是最短序列长度。

复杂度

朴素变字母 BFS: 时间 O(N · L²) · 空间 O(N)
通配符建桶: 时间 O(N · L²) · 空间 O(N · L)

N = 单词数量，L = 单词长度。朴素变字母 BFS 每个词尝试 L×26 种变换；通配符建桶额外存 L 个桶。

面试回答

把 wordList 放进 wordSet；若 endWord 不在集合里直接返回 0。beginWord 入队，level=1，visited 入队时标记。每层 size:=len(queue) 固定当前层，逐词出队，对每个位置尝试 a-z 生成 next；next 在 wordSet 且未访问则入队并标记 visited。出队词等于 endWord 时返回 level。朴素变字母：时间 O(N·L²)，空间 O(N)；通配符建桶：时间 O(N·L²)，空间 O(N·L)。

常见错误

把答案写成变化次数 4，而不是序列长度 5

hit→hot→dot→dog→cog 共 5 个单词；题目要的是序列长度，不是边数。

忘记判断 endWord 是否在 wordList

endWord 不在 wordSet 时无法到达，应直接返回 0，否则 BFS 白跑。

visited 出队时才标记，导致重复入队

同一单词可能被多个邻居重复加入 queue，层数和队列都会膨胀。应在入队时立刻标记。

每次都暴力两两比较单词，复杂度过高

O(N²·L) 两两比较在大列表会 TLE；应改字母查 wordSet 或通配符桶。

没有按层处理，level 加错位置

level++ 应放在内层 for 结束后（整层处理完再加），不能每出队一个词就加。