LeetCode LCR 108. 单词接龙

2026-03-28 HGNULB 约 6 分钟

文章信息 5 个分类 4 个标签

分类

LeetCode 困难 119 经典题变种挑战剑指 Offer 剑指 Offer（专项突击版）

题目描述

✅ LCR 108. 单词接龙

题意分析

从 beginWord 出发，每次恰好替换一个小写字母，得到的新单词必须在字典中，求到 endWord 的最短转换序列包含多少个单词。答案包含起点和终点，不是替换次数；无法到达时返回 0。

题目保证两个端点等长且不同。起点不必在字典中，终点必须在字典中。把单词看成节点、一次合法替换看成一条单位边，就得到隐式图上的最短路问题。

解法：BFS 枚举单字符替换

核心思路

[!blue]

使用 BFS 从起点逐层扩展。answer 表示当前层的路径单词数，初值为 1；每处理完整一层再加一。因此从当前层生成终点时，它的序列长度就是 answer+1。

邻居不必通过两两比较字典单词建立。对当前单词的每个位置，依次尝试替换成 a..z，再检查候选是否在尚未访问的字典中。每个位置尝试完后恢复原字符，使下一个位置的枚举仍然只改变一位。

字典同时保存访问状态。Java 在单词入队时删除它，Go 将对应布尔值置为 false；两者都表示以后不再接受这个候选。起点在开始时也被移除，避免字典本来包含起点时把它再次加入队列。

BFS 按路径长度从短到长展开，单词首次入队时已经得到最短距离。之后沿其他路径再到达它，距离不会更小，而它能继续转换出的单词只由自身决定，所以跳过重复状态不会漏掉更短答案。入队时立即标记，还能阻止同层其他节点重复加入同一单词。

候选先通过字典与访问检查，再判断是否为终点，因此只有合法转换才能返回答案。代码虽然也会枚举原字符，生成不变的原词，但当前词已经被标记访问，这个零次修改候选会被跳过。队列耗尽仍未找到终点时，返回 0。

解题步骤

将字典装入集合或布尔映射，移除起点，队列仅加入 beginWord，令 answer = 1。

每层开始时固定当前队列长度，只处理这些单词，新加入的候选留给下一层。

对出队单词逐位置枚举替换字母，过滤不在字典或已经访问的候选。

合法候选等于终点时返回 answer+1，否则入队并立即标记访问；每个位置结束后恢复原字符。

当前层处理完后增加 answer。队列为空仍未命中则返回零，终点不在字典时也会得到这一结果。

代码实现

class Solution {

    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        Set<String> words = new HashSet<>(wordList);

        words.remove(beginWord);
        Queue<String> q = new LinkedList<>();

        q.offer(beginWord);
        // answer 表示当前层对应的序列长度，beginWord 自身算一个。
        int answer = 1;

        while (!q.isEmpty()) {
            // 先固定本层大小，避免与下一层混在一起。
            for (int i = q.size(); i > 0; --i) {
                String s = q.poll();
                char[] chars = s.toCharArray();

                for (int j = 0; j < chars.length; ++j) {
                    char ch = chars[j];

                    for (char k = 'a'; k <= 'z'; ++k) {
                        chars[j] = k;
                        String t = new String(chars);

                        // 不在词典中，或已被访问过（访问后即删除）。
                        if (!words.contains(t)) {
                            continue;
                        }

                        if (endWord.equals(t)) {
                            return answer + 1;
                        }

                        q.offer(t);
                        // 入队即标记，防止同一单词被重复展开。
                        words.remove(t);
                    }

                    // 还原本位，避免污染后续位置的枚举。
                    chars[j] = ch;
                }
            }

            ++answer;
        }

        return 0;
    }
}

func ladderLength(beginWord string, endWord string, wordList []string) int {
    words := make(map[string]bool)
    for _, word := range wordList {
        words[word] = true
    }
    delete(words, beginWord)
    q := []string{
        beginWord,
    }
    // answer 表示当前层对应的序列长度，beginWord 自身算一个。
    answer := 1
    for len(q) > 0 {
        // 先固定本层大小，避免与下一层混在一起。
        for i := len(q); i > 0; i-- {
            s := q[0]
            q = q[1:]
            chars := []byte(s)
            for j := 0; j < len(chars); j++ {
                ch := chars[j]
                for k := 'a'; k <= 'z'; k++ {
                    chars[j] = byte(k)
                    t := string(chars)
                    // 不在词典中，或已被访问过（访问后即删除）。
                    if !words[t] {
                        continue
                    }
                    if t == endWord {
                        return answer + 1
                    }
                    q = append(q, t)
                    // 入队即标记，防止同一单词被重复展开。
                    words[t] = false
                }
                // 还原本位，避免污染后续位置的枚举。
                chars[j] = ch
            }
        }
        answer++
    }
    return 0
}

复杂度分析

设字典单词数为 N，每个单词长度为 L。

时间复杂度：期望 $O(26NL^2)$。每个单词最多展开一次，每次枚举 26L 个候选；构造候选字符串和计算哈希都需要 $O(L)$，不能把字符串成员查询当作与词长无关的常数操作。

空间复杂度：$O(NL)$。字典与队列保存至多线性数量的单词，当前字符数组只需 $O(L)$。

关键点总结

[!green]

单位边上的 BFS 保证首次入队距离最短，重复到达同一个单词无需重新展开。

候选由单字符替换现场生成，字典成员检查同时验证合法性和是否访问。

Java 删除键、Go 将值置假，都是将单词从尚可使用的状态集合中移除。

层号统计单词个数，起点占一个；在下一层生成终点时返回当前值加一。

易错点总结

[!yellow]

用变换次数作为答案，会漏掉起点这一项。

层内反复读取变化的队列长度，会把刚加入的下一层也当成本层处理。

不恢复被替换位置的原字符，会在后续位置枚举中累积多处修改。

生成终点就直接返回却不检查字典，可能接受题目不允许的单词。

等到出队才标记，或忘记在开始时排除起点，会造成重复状态入队。

相似题目

题目	难度	关联与区别
433. 最小基因变化	中等	同样在单字符变化构成的状态图上求最少变化，原题基因串固定长度且候选较少。
126. 单词接龙 II	困难	同样求最短单词变化，原题还需保留所有最短前驱以输出全部路径。

.article-image.is-loading { width: var(--article-image-width, 100%); height: auto; } .article-image.is-loading img { position: static; width: auto !important; height: auto !important; opacity: 1; pointer-events: auto; } .article-image-spinner { display: none; }

转载与许可

作者 HGNULB

链接 https://hgnulb.github.io/blog/2026/70647342

许可本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！