单词接龙为什么用 BFS 求最短转换序列？

简化版

单词接龙把每个单词看成图节点，两个单词只差一个字符就连边。题目要求最少转换次数，所以用 BFS 按层扩展；第一次到达 endWord 的层数就是最短长度。

详细版

朴素做法是每次枚举当前单词的每个位置，把字符替换成 a-z，如果新单词在字典中且没访问过，就入队。BFS 队列里存单词和步数，起点步数为 1。为了避免重复访问，要把入队后的单词从字典或 visited 中标记掉。

优化做法是预处理通配模式，例如 hot 生成 *ot、h*t、ho*，同模式下的单词互为邻居。这样可以减少反复构造邻居的成本。复杂度通常按单词数 N、单词长度 L 分析，通配建图约 O(NL)。

完整版教学

一、为什么这是图最短路

每个合法单词是一个节点，如果两个单词长度相同且只有一个字符不同，就可以一步转换，也就是一条无权边。要求从 beginWord 到 endWord 的最少转换次数，本质就是无权图最短路径。

hit -> hot -> dot -> dog -> cog
           \-> lot -> log -> cog

所有边的成本都是 1，所以 BFS 是天然选择。Dijkstra 也能求无权最短路，但多余；DFS 会先走深路径，不保证第一次找到的是最短。

二、BFS 层数代表转换长度

BFS 一层一层扩展，第一层是起点，第二层是一步可达单词，第三层是两步可达单词。第一次遇到终点时，当前层数就是最短转换序列长度。

层数	单词例子	含义
1	hit	起点
2	hot	转换 1 次
3	dot, lot	转换 2 次
4	dog, log	转换 3 次
5	cog	转换 4 次，序列长度 5

注意题目常返回的是序列中单词数量，不是边数，所以起点层数通常记为 1。如果问转换次数，则答案应是层数减 1。

三、枚举邻居的直接写法

直接写法不需要预建完整图。对当前单词的每个位置，尝试替换成 26 个字母，形成新单词，如果在字典里就是邻居。

int ladderLength(String begin, String end, List<String> wordList) {
    Set<String> dict = new HashSet<>(wordList);
    if (!dict.contains(end)) return 0;
    Queue<String> q = new ArrayDeque<>();
    q.offer(begin);
    int steps = 1;
    while (!q.isEmpty()) {
        for (int size = q.size(); size > 0; size--) {
            String cur = q.poll();
            if (cur.equals(end)) return steps;
            char[] arr = cur.toCharArray();
            for (int i = 0; i < arr.length; i++) {
                char old = arr[i];
                for (char ch = 'a'; ch <= 'z'; ch++) {
                    arr[i] = ch;
                    String next = new String(arr);
                    if (dict.remove(next)) q.offer(next);
                }
                arr[i] = old;
            }
        }
        steps++;
    }
    return 0;
}

这里用 dict.remove(next) 同时完成“判断存在”和“标记访问”。入队时就删除，能避免同一层或后续层重复入队。

四、通配模式如何优化

通配模式把“只差一个字符”的关系转成中间桶。例如 hot 的模式是 *ot、h*t、ho*，dot 和 lot 都在 *ot 桶里，所以它们都是 hot 的邻居。

*ot -> hot, dot, lot
d*g -> dog, dug
ho* -> hot, hog

预处理 N 个单词，每个单词生成 L 个模式，总共 O(NL) 个插入。BFS 时通过当前单词的 L 个模式找到候选邻居，避免每次做 26L 次字符串构造。在词表很大时，这种方式更常见。

五、双向 BFS 为什么更快

普通 BFS 从起点向外扩展，分支多时节点数增长很快。双向 BFS 同时从 begin 和 end 两端扩展，每次扩展较小的一侧，直到两边相遇。

单向: b^d
双向: b^(d/2) + b^(d/2)

如果分支因子 b=10、最短深度 d=6，单向大约可能扩到 10^6 量级，双向两边各扩到 10^3 量级，差距明显。面试中先写普通 BFS，再说明双向 BFS 优化，会比较稳。

六、边界条件与复杂度

如果 endWord 不在词表里，经典题直接返回 0。beginWord 不一定在词表中，但可以作为 BFS 起点。所有单词长度通常相同，否则“一次改变一个字符”的建边规则不成立。

写法	时间复杂度粗略口径	空间
枚举 26 字母	O(N * L * 26) 到 O(N * L * 26 * 字符串成本)	O(N)
通配模式	O(NL + BFS 邻居扫描)	O(NL)
双向 BFS	最坏仍可能很高，平均显著减少搜索	O(N)

复杂度口径不必死抠常数，重点是说明每个单词尽量只入队一次，visited 是避免爆炸的关键。

七、常见误区与追问

记忆钩子：单词接龙是“无权图最短路”，看到最少转换次数就先想到 BFS 层序。

误区：用 DFS 找到终点就返回。 DFS 第一次找到的路径不一定最短，除非额外做全局最小搜索，代价很高。
误区：访问标记在出队时才做。 同一个单词可能被同一层多个父节点重复入队，通常入队时就标记。
误区：返回转换边数而不是序列长度。 经典题返回包含 begin 和 end 的单词数量，起点层数应为 1。
追问：为什么 endWord 不在词表返回 0？ 因为每次转换后的中间词和终点都必须来自词表，终点不存在就无法到达。
追问：如何输出所有最短路径？ 需要 BFS 建父节点关系，并只保留最短层，再回溯生成路径。
追问：如何优化大词表？ 用通配模式或双向 BFS，减少邻居枚举和搜索层数。

八、加强记忆

单词接龙的关键是建模：单词是节点，一次改一个字符是无权边，最少转换就是 BFS 最短路。普通 BFS 要在入队时标记访问，层数从 1 开始。词表大时，用通配桶快速找邻居；搜索深时，用双向 BFS 缩小扩展范围。

简化版

详细版