Word Ladder 最短变换路径全解：BFS 图建模与通配符模式建边（leetcode 仓库实战）

【免费下载链接】leetcode Leetcode solutions 项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode

导读

本文基于仓库中的 hints/word-ladder.md 提示文档，系统讲解 LeetCode 127「单词接龙」（Word Ladder）的完整求解思路：如何把"每次改变一个字符、逐步从 beginWord 变换到 endWord"的问题抽象成无权图上的最短路径问题，如何借助 * 通配符模式在 O(m²·n) 时间内高效建边，以及如何用 BFS 保证找到最短变换序列。读完本文，你将掌握三种标准 BFS 实现与一种双向 BFS 进阶优化，并能对照仓库中 Python、Java、C++、Go、Rust 等 12 种语言的 0127-word-ladder 源码快速落地。

---

1. 问题定义：从"一个字符的差距"到最短变换序列

LeetCode 127 的输入与要求如下：

• 输入：起始词 beginWord、目标词 endWord、字典 wordList；
• 规则：每一步只能把当前词的一个字符替换成另一个小写字母，且变换后的词必须出现在 wordList 中；
• 输出：从 beginWord 到 endWord 的最短变换序列包含的单词个数；如果不存在这样的序列，返回 0。

经典示例：beginWord = "hit"，endWord = "cog"，wordList = ["hot","dot","dog","lot","log","cog"]，最短序列为 hit → hot → dot → dog → cog，共 5 个单词，因此答案是 5。

注意这里返回的是"序列中的单词个数"，即节点数而不是变换次数（边数）。这一语义直接决定了计数器初始化的方式，也是下文常见陷阱中第一个 off-by-one 问题的来源。

---

2. Hint 1 展开：把问题建模为无权图上的最短路径

提示文档的第一条 hint 给出的核心洞察是：

把每个字符串看作一个节点，两个字符串仅相差一个字符时在它们之间连一条边。

这样一来，原问题就等价于：在一张以单词为节点、以"相差一个字符"为边的无权图上，求从 beginWord 到 endWord 的最短路径长度（节点数）。由于图中每条边权重相同（都为 1），BFS 的层序扩展天然保证：所有距离为 k 的节点会先于距离为 k+1 的节点被访问，因此第一次遇到 endWord 时的层数一定是最短距离。

hint 1 还指出了一种"朴素建边"思路及其低效之处：

朴素做法是枚举每一对字符串并检查它们之间能否构成一条边。

两两比较所有词对需要 O(n²) 次比较，每次比较逐字符扫描长度为 m 的词，总代价为 O(n²·m)。当 wordList 较大时（LeetCode 127 的词表规模可达数千），这一开销不可接受。文章 articles/word-ladder.md 第 1 节 "Breadth First Search - I" 正是这种朴素建边 + BFS 的实现，其复杂度为 O(n²·m) 时间、O(n²) 空间。它思路直观，但并非本题的最优解法。

hint 1 随后给出了一个更有启发性的思考方向：

考虑字符串 hot，思考通过改变一个字母可以得到哪些字符串。

这就引出了 hint 2 的通配符模式建边法。

---

3. Hint 2 展开：用 * 通配符模式高效建边

3.1 核心思想：把"一个字符不同"变成"共享同一个模式"

hint 2 给出的关键技巧是：

把每个单词中某一位置的字符替换为通配符 *，得到若干中间状态（pattern）。这些中间状态充当"父节点"，把只相差一个字符的单词连接到一起。

以 hot 为例，它可以生成三个模式：

hot → *ot
hot → h*t
hot → ho*

所有共享同一模式的单词之间恰好相差一个字符。例如模式 *ot 可以把 hot 和 cot 连在一起，模式 h*t 可以把 hot 和 hat 连在一起。模式桶（pattern bucket）就替代了显式的邻接表：无需两两比较，只要查一下当前词对应模式下的所有词，就能在 O(1) 平均代价内拿到全部邻居。

hint 2 明确给出了预处理与搜索的整体安排：

对列表中的每个单词，用 * 替换每个位置的字符生成所有可能的模式，并把该单词登记为这些模式的孩子；然后从 beginWord 出发运行 BFS，用哈希集合避免重复访问。

3.2 数据结构：Map<pattern, List<word>>

建边阶段只需要一个哈希映射，键是模式字符串（如 *ot），值是属于该模式的所有单词：

模式	桶内单词
*ot	hot, cot, ...
h*t	hot, hat, ...
ho*	hot, how, ...

用 Python 的 collections.defaultdict(list) 可以一行完成分组逻辑，仓库实现 python/0127-word-ladder.py 的预处理部分如下：

nei = collections.defaultdict(list)
wordList.append(beginWord)          # 把起始词也纳入建图
for word in wordList:
    for j in range(len(word)):
        pattern = word[:j] + "*" + word[j + 1 :]
        nei[pattern].append(word)

这里把 beginWord 也加入 wordList 一并建图，是为了让起始词同样能通过模式桶找到邻居，而 endWord 天然已经在词表中（若不在，则直接返回 0，见第 6 节陷阱二）。整个预处理的时间为 O(m·n)（每个词生成 m 个模式），空间为 O(m·n)（桶内共存放 n·m 个词项）。

---

4. Hint 3 展开：BFS 搜索主循环与返回语义

4.1 逐层扩展

hint 3 描述了 BFS 主循环的完整行为：

BFS 访问一个节点时，如果当前词匹配 endWord，立即返回；否则，生成当前词的所有模式，尝试访问这些模式连接到的、尚未访问过的单词，仅把未访问的词加入队列。

对应仓库 python/0127-word-ladder.py 的搜索部分：

visit = set([beginWord])
q = deque([beginWord])
res = 1
while q:
    for i in range(len(q)):
        word = q.popleft()
        if word == endWord:
            return res
        for j in range(len(word)):
            pattern = word[:j] + "*" + word[j + 1 :]
            for neiWord in nei[pattern]:
                if neiWord not in visit:
                    visit.add(neiWord)
                    q.append(neiWord)
    res += 1
return 0

几个关键点：

• 层计数 res 从 1 开始：因为序列至少包含 beginWord 本身，res 统计的是"当前正在处理的层 = 从 beginWord 出发的节点数（含起点）"；每处理完一层 res += 1。
• visit 集合即 hint 2 提到的哈希集合：BFS 首次到达某个词的层数一定是最短的，因此访问过的词无需再入队；同时用它作为"已消费词"标记，避免死循环与重复扩展。
• 命中即返回：在入队阶段就判断 word == endWord，一旦命中立即返回当前 res，无需再扩展其邻居。

4.2 关于 hint 中 true/false 的说明

hint 3 在描述搜索结果时使用了 return true / return false 的表述，这是为了示意"找到 / 未找到"的判定逻辑。但在 LeetCode 127 的真实接口中，ladderLength 返回的是 int：找到 endWord 时返回当前层数（最短序列的单词个数），队列耗尽仍未找到时返回 0。仓库中所有语言的实现均遵循这一返回语义，例如 go/0127-word-ladder.go 在 for len(q) != 0 循环结束后返回 0。

4.3 为什么 BFS 一定给出最短路径

由于每次扩展只走"一步"（改变一个字符），BFS 天然按距离分层推进：第 k 层的所有词到 beginWord 的最短距离都是 k。第一次遇到 endWord 时它所在的层数就是最短变换长度。反之，DFS 虽然能找到一条可行路径，但无法保证它最短（详见第 6 节陷阱五）。

---

5. 复杂度分析：为什么提示推荐 O((m²)·n)

hints 文档开头给出的目标复杂度为：

时间 O((m²)·n)，空间 O((m²)·n)，其中 n 是单词个数，m 是单词长度。

这一复杂度对应的是"动态生成邻居"与"通配符模式桶"两类做法，而非"两两比较建邻接表"。三种主流实现的开销对比如下（n = 词数，m = 词长）：

方案	建边/邻居策略	时间	空间
I. 预计算邻接表（两两比较）	枚举所有词对，逐字符比较	O(n²·m)	O(n²)
II. 逐字符动态生成邻居	每个词尝试替换 26 个字母 × m 个位置	O(m²·n)	O(m²·n)
III. 通配符模式桶	模式预计算，BFS 中查桶	O(m²·n)	O(m²·n)
IV. 双向 BFS（Meet in the Middle）	两端交替扩展较小边界	O(m²·n)	O(m²·n)

各方案时间复杂度推导要点：

• 方案 I：两两比较 n² 对 × 每对比较 m 个字符 → O(n²·m)。当词表规模远大于词长时（n >> m），这是最差的选择。
• 方案 II：每个词生成邻居时，m 个位置 × 26 个字母，每次生成新字符串代价 O(m) → 每个词 O(26·m²)，共 O(m²·n)。
• 方案 III：每个词生成 m 个模式并查桶；桶内所有词项总数是 O(n·m)，BFS 全程对每个词项至多访问一次 → O(m²·n) 的宽松上界（m 次模式查找 × 平均桶规模）。
• 方案 IV：本质上复用方案 II 的邻居生成，但由于两端同时向中间推进，实际扩展的节点数大幅减少，复杂度上界仍记作 O(m²·n)，常数远小于单向 BFS。

时间与空间的取舍也值得注意：方案 I 的邻接表虽然空间是 O(n²)，但建图时间最贵；方案 III 用 O(m·n) 的模式桶空间换来了 BFS 阶段近乎 O(1) 的邻居查询，是提示文档推荐的综合最优解，也是仓库默认实现的选型（见 python/0127-word-ladder.py）。

---

6. 四种实现方案详解（源码佐证）

以下四种方案均收录于文章 articles/word-ladder.md，并与仓库各语言源码一一对应。为便于阅读，这里统一给出 Python 版本，其余语言实现路径见第 7 节。

方案一：预计算邻接表（两两比较）+ BFS

思路最直观：先建 Map<word, index> 映射，再两两比较所有词对，相差恰好一个字符的词互连为邻接表，最后 BFS 求最短距离。代价是建图 O(n²·m)。

class Solution:
    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
        if (endWord not in wordList) or (beginWord == endWord):
            return 0

        n, m = len(wordList), len(wordList[0])
        adj = [[] for _ in range(n)]
        mp = {}
        for i in range(n):
            mp[wordList[i]] = i

        for i in range(n):
            for j in range(i + 1, n):
                cnt = 0
                for k in range(m):
                    if wordList[i][k] != wordList[j][k]:
                        cnt += 1
                if cnt == 1:
                    adj[i].append(j)
                    adj[j].append(i)

        q, res = deque(), 1
        visit = set()
        for i in range(m):
            for c in range(97, 123):
                if chr(c) == beginWord[i]:
                    continue
                word = beginWord[:i] + chr(c) + beginWord[i + 1:]
                if word in mp and mp[word] not in visit:
                    q.append(mp[word])
                    visit.add(mp[word])

        while q:
            res += 1
            for i in range(len(q)):
                node = q.popleft()
                if wordList[node] == endWord:
                    return res
                for nei in adj[node]:
                    if nei not in visit:
                        visit.add(nei)
                        q.append(nei)

        return 0

复杂度：时间 O(n²·m)，空间 O(n²)。

方案二：逐字符动态生成邻居 + BFS

不预建图，把 wordList 转成 set，BFS 过程中对每个词尝试替换 m 个位置、每个位置尝试 26 个字母，命中集合中的词即为邻居，同时从集合中删除该词以完成"访问标记"。

class Solution:
    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
        if (endWord not in wordList) or (beginWord == endWord):
            return 0
        words, res = set(wordList), 0
        q = deque([beginWord])
        while q:
            res += 1
            for _ in range(len(q)):
                node = q.popleft()
                if node == endWord:
                    return res
                for i in range(len(node)):
                    for c in range(97, 123):
                        if chr(c) == node[i]:
                            continue
                        nei = node[:i] + chr(c) + node[i + 1:]
                        if nei in words:
                            q.append(nei)
                            words.remove(nei)
        return 0

复杂度：时间 O(m²·n)，空间 O(m²·n)。注意此处 res 从 0 开始、入队即返回命中值，与方案三的计数方式略有差异，但最终答案一致。

方案三：通配符模式桶 + BFS（hints 推荐方案）

这是提示文档 hint 2/hint 3 描述的完整落地，也是仓库默认实现 python/0127-word-ladder.py 的代码（上文第 3、4 节已逐段讲解，此处给出完整版）：

class Solution:
    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
        if endWord not in wordList:
            return 0

        nei = collections.defaultdict(list)
        wordList.append(beginWord)
        for word in wordList:
            for j in range(len(word)):
                pattern = word[:j] + "*" + word[j + 1 :]
                nei[pattern].append(word)

        visit = set([beginWord])
        q = deque([beginWord])
        res = 1
        while q:
            for i in range(len(q)):
                word = q.popleft()
                if word == endWord:
                    return res
                for j in range(len(word)):
                    pattern = word[:j] + "*" + word[j + 1 :]
                    for neiWord in nei[pattern]:
                        if neiWord not in visit:
                            visit.add(neiWord)
                            q.append(neiWord)
            res += 1
        return 0

复杂度：时间 O(m²·n)，空间 O(m²·n)。Java 版本可参考 java/0127-word-ladder.java，它同样用 Map<String, List<String>> 构造模式桶；Rust 版本 rust/0127-word-ladder.rs 用 HashMap<String, Vec<String>> 实现相同逻辑。

方案四：双向 BFS（Meet in the Middle）

标准 BFS 的搜索空间随距离呈指数增长。hint 之外的进阶优化是：同时从 beginWord 与 endWord 两端做 BFS，在中间相遇，从而把搜索深度减半。核心技巧是每轮只扩展较小的一侧边界（qb vs qe，以及配套的距离表 fromBegin / fromEnd 同步交换），以平衡工作量；一旦当前词生成的邻居出现在另一侧的已访问表中，就返回 steps + fromEnd[nei]。

class Solution:
    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
        if endWord not in wordList or beginWord == endWord:
            return 0
        m = len(wordList[0])
        wordSet = set(wordList)
        qb, qe = deque([beginWord]), deque([endWord])
        fromBegin, fromEnd = {beginWord: 1}, {endWord: 1}

        while qb and qe:
            if len(qb) > len(qe):
                qb, qe = qe, qb
                fromBegin, fromEnd = fromEnd, fromBegin
            for _ in range(len(qb)):
                word = qb.popleft()
                steps = fromBegin[word]
                for i in range(m):
                    for c in range(97, 123):
                        if chr(c) == word[i]:
                            continue
                        nei = word[:i] + chr(c) + word[i + 1:]
                        if nei not in wordSet:
                            continue
                        if nei in fromEnd:
                            return steps + fromEnd[nei]
                        if nei not in fromBegin:
                            fromBegin[nei] = steps + 1
                            qb.append(nei)
        return 0

复杂度：时间 O(m²·n)、空间 O(m²·n)（上界），实际扩展节点数显著小于单向 BFS，是词表较大时最推荐的进阶方案。

---

7. 常见陷阱（源自文章 Common Pitfalls 一节）

陷阱一：返回"变换次数"而不是"单词个数"

题目要求返回序列中的单词数（节点数）。若 res 从 0 开始计数，返回的将是边数，答案会比正确值少 1：

# 错误：res 从 0 开始，统计的是变换次数（边数）
res = 0
while q:
    res += 1
    # ...
    if word == endWord:
        return res  # 少 1

# 正确：res 从 1 开始，把 beginWord 计入节点数
res = 1

陷阱二：忘记先检查 endWord 是否在 wordList 中

endWord 不在词表中时，变换不可能完成。所有方案的 Python 实现都以 if endWord not in wordList: return 0 作为第一道守卫，跳过不必要的 BFS 遍历，同时避免返回错误结果。

陷阱三：出队时才标记 visited

先入队、出队时再标记"已访问"，会导致同一个词从多个邻居被重复加入队列，产生重复处理与错误的距离计算。正确做法是入队的同时立即标记：

# 错误：出队时才标记，队列中已出现重复
node = q.popleft()
visit.add(node)

# 正确：入队时立即标记
if nei in words and nei not in visit:
    visit.add(nei)  # 立即标记
    q.append(nei)

陷阱四：生成邻居时未跳过原字符

逐位置替换字母时，若不对 c == word[i] 的情况 continue，会把原词本身当作"邻居"加入队列，形成自环并污染结果：

for c in 'abcdefghijklmnopqrstuvwxyz':
    if c == word[i]:
        continue  # 跳过原字符
    nei = word[:i] + c + word[i + 1:]

陷阱五：用 DFS 求最短路径

DFS 找到的是一条路径，但不保证最短。本题必须用 BFS，因为 BFS 按层推进，首次命中即最短：

# 错误：DFS 返回的第一条路径不一定是全局最短
def dfs(word, depth):
    if word == endWord:
        return depth
    for nei in getNeighbors(word):
        result = dfs(nei, depth + 1)
        if result:
            return result

# 正确：BFS 首次命中即最短
while q:
    word = q.popleft()
    if word == endWord:
        return distance[word]  # 保证最短

---

8. 仓库中的多语言实现索引

本仓库对 LeetCode 127 提供了 12 种语言的完整实现，均位于根目录下对应语言子目录，方便对照阅读与交叉验证：

语言	文件路径
Python	python/0127-word-ladder.py
Java	java/0127-word-ladder.java
C++	cpp/0127-word-ladder.cpp
JavaScript	javascript/0127-word-ladder.js
TypeScript	typescript/0127-word-ladder.ts
Go	go/0127-word-ladder.go
Rust	rust/0127-word-ladder.rs
C#	csharp/0127-word-ladder.cs
Kotlin	kotlin/0127-word-ladder.kt
Swift	swift/0127-word-ladder.swift
C	c/0004-median-of-two-sorted-arrays.c（本仓库 C 语言目录暂未收录该题）
Ruby / Dart / Scala	本仓库对应目录暂未收录该题

从源码结构看，Python、Go、Java 等实现均采用"通配符模式桶 + BFS"这一提示文档推荐的核心思路；对比 go/0127-word-ladder.go 与 python/0127-word-ladder.py 可以发现，两者在模式生成、visit 标记与层计数逻辑上完全一致，仅语言语法不同。如需完整的多解法详解与各语言代码，可进一步阅读 articles/word-ladder.md。

---

9. 总结

回顾 hints 文档给出的三条核心提示，可以提炼出本题的完整解题链：

1. 图建模（Hint 1）：单词是节点，"相差一个字符"是边，问题转化为无权图最短路径，BFS 保证最短性；
2. 通配符建边（Hint 2）：用 *ot、h*t、ho* 这类模式把相差一个字符的词分组进桶，以 O(m·n) 的预计算换取 BFS 阶段近乎 O(1) 的邻居查找；
3. BFS 搜索（Hint 3）：从 beginWord 出发逐层扩展，用哈希集合去重，命中 endWord 即返回层数，队列耗尽返回 0，整体复杂度控制在推荐的 O((m²)·n) 时间与空间内。

在此基础上，双向 BFS 通过"两端扩展、小边优先"把搜索空间进一步压缩，是应对大规模词表的最佳实践。对照仓库中 12 种语言的 0127-word-ladder 实现逐一推演，即可彻底掌握这类"隐式图 + BFS"题型的通用解法。

【免费下载链接】leetcode Leetcode solutions 项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode