跳至主要內容

单词接龙——双向BFS的剪枝优化从TLE到AC

老张2026/4/30大约 7 分钟

单词接龙——双向BFS的剪枝优化从TLE到AC

适读人群：Java 后端工程师、准备大厂面试的同学 | 阅读时长：约25分钟 | 难度：Hard

开篇故事

127 题（单词接龙）是我见过的图的题目里，最能考察 BFS 优化能力的一道。

这道题用单向 BFS 很容易写出来，但在极端用例下会 TLE。我第一次提交就 TLE 了，看了看数据规模：wordList 最多 5000 个单词，每个单词最长 10 个字符。单向 BFS 最坏情况要遍历整个单词表，每个单词生成所有变体来找邻居，这个开销不小。

后来研究了双向 BFS（Bidirectional BFS），才真正过了。双向 BFS 同时从 beginWord 和 endWord 出发，两边各扩展一层，当两个前沿集合有交集时，就找到了最短路径。

双向 BFS 为什么更快？单向 BFS 假设最短路径长度为 d，BFS 遍历的节点数约为 O(b^d)（b 是分支因子）。双向 BFS 各走 d/2 步，遍历节点数约为 2 * O(b^(d/2))，当 b^(d/2) << b^d 时，节省非常显著。

这是图算法里一个非常实用的优化技巧，值得专门讲一篇。

一、题目解析

题目：LeetCode 127. 单词接龙

字典 wordList 中从单词 beginWord 到 endWord 的转换序列，每次转换只能改变一个字母，且转换后的单词必须在字典中。返回从 beginWord 到 endWord 的最短转换序列中的单词数目，如果不存在，返回 0。

示例：

输入：beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]
输出：5
解释：hit -> hot -> dot -> dog -> cog，共5个单词

输入：beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log"]
输出：0（endWord "cog" 不在字典中）

约束：

  • 1 <= beginWord.length <= 10
  • endWord.length == beginWord.length
  • 1 <= wordList.length <= 5000
  • wordList[i].length == beginWord.length

二、解法一：单向 BFS（基础版）

思路

把每个单词看作图的一个节点，两个单词之间如果只差一个字母，就有一条边（无向）。问题转化为：从 beginWord 到 endWord 的最短路径（BFS 找最短路）。

用 BFS 逐层扩展，每次把当前层的所有单词扩展到所有可能的下一个单词（通过依次改变每个字母位置的每个字母），找到 endWord 时返回当前层数。

完整代码

class Solution {
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        Set<String> wordSet = new HashSet<>(wordList);
        if (!wordSet.contains(endWord)) return 0;
        
        Queue<String> queue = new LinkedList<>();
        queue.offer(beginWord);
        Set<String> visited = new HashSet<>();
        visited.add(beginWord);
        int level = 1;
        
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                String word = queue.poll();
                char[] chars = word.toCharArray();
                
                for (int j = 0; j < chars.length; j++) {
                    char originalChar = chars[j];
                    for (char c = 'a'; c <= 'z'; c++) {
                        if (c == originalChar) continue;
                        chars[j] = c;
                        String newWord = new String(chars);
                        if (newWord.equals(endWord)) return level + 1;
                        if (wordSet.contains(newWord) && !visited.contains(newWord)) {
                            visited.add(newWord);
                            queue.offer(newWord);
                        }
                    }
                    chars[j] = originalChar;  // 还原
                }
            }
            level++;
        }
        
        return 0;
    }
}

复杂度分析

设单词长度为 L，字典大小为 N。

  • 时间复杂度：O(N * L * 26) = O(N * L)。每个单词生成 L * 26 个候选，共 N 个单词。
  • 空间复杂度：O(N * L)。visited 集合和队列。

在最坏情况下（最短路径很长），实际遍历的节点接近整个字典，可能 TLE。

三、解法二：预处理邻居（加速边的查找）

思路

单向 BFS 里，每次扩展一个单词，都要遍历 L * 26 个候选，然后检查是否在字典里。可以预先构建通用模式到单词列表的映射，加速邻居查找。

例如，"hot" 的通用模式是 "ot"、"ht"、"ho*"，凡是匹配这些模式的单词都是 "hot" 的邻居。

class Solution {
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        int L = beginWord.length();
        
        // 建立通用模式到单词的映射
        Map<String, List<String>> allComboDict = new HashMap<>();
        for (String word : wordList) {
            for (int i = 0; i < L; i++) {
                String newWord = word.substring(0, i) + '*' + word.substring(i + 1);
                allComboDict.computeIfAbsent(newWord, k -> new ArrayList<>()).add(word);
            }
        }
        
        Queue<String> queue = new LinkedList<>();
        queue.offer(beginWord);
        Map<String, Integer> visited = new HashMap<>();
        visited.put(beginWord, 1);
        
        while (!queue.isEmpty()) {
            String word = queue.poll();
            int currLevel = visited.get(word);
            
            for (int i = 0; i < L; i++) {
                String pattern = word.substring(0, i) + '*' + word.substring(i + 1);
                for (String neighbor : allComboDict.getOrDefault(pattern, new ArrayList<>())) {
                    if (neighbor.equals(endWord)) return currLevel + 1;
                    if (!visited.containsKey(neighbor)) {
                        visited.put(neighbor, currLevel + 1);
                        queue.offer(neighbor);
                    }
                }
            }
        }
        
        return 0;
    }
}

复杂度分析

  • 时间复杂度：O(N * L^2)。预处理 O(N * L^2)（每个单词的每个模式用 substring 是 O(L)），BFS O(N * L)。
  • 空间复杂度：O(N * L^2)。存储所有模式。

四、解法三：最优解法——双向 BFS

思路

双向 BFS：

  • 同时从 beginWord 和 endWord 出发，各维护一个"前沿集合"
  • 每次选择较小的那个前沿集合进行扩展（关键优化！）
  • 扩展时，如果新节点出现在另一侧的前沿集合中，找到了最短路径

关键细节：每次选较小的集合扩展，可以最大程度地平衡两边的搜索规模，最小化总遍历节点数。

Mermaid 图——双向 BFS 原理

完整代码

class Solution {
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        Set<String> wordSet = new HashSet<>(wordList);
        if (!wordSet.contains(endWord)) return 0;
        
        Set<String> beginSet = new HashSet<>();
        Set<String> endSet = new HashSet<>();
        beginSet.add(beginWord);
        endSet.add(endWord);
        Set<String> visited = new HashSet<>();
        visited.add(beginWord);
        visited.add(endWord);
        
        int level = 1;
        
        while (!beginSet.isEmpty() && !endSet.isEmpty()) {
            // 每次扩展较小的集合（关键优化）
            if (beginSet.size() > endSet.size()) {
                Set<String> temp = beginSet;
                beginSet = endSet;
                endSet = temp;
            }
            
            Set<String> nextSet = new HashSet<>();
            
            for (String word : beginSet) {
                char[] chars = word.toCharArray();
                for (int j = 0; j < chars.length; j++) {
                    char original = chars[j];
                    for (char c = 'a'; c <= 'z'; c++) {
                        chars[j] = c;
                        String newWord = new String(chars);
                        if (endSet.contains(newWord)) return level + 1;  // 相遇
                        if (wordSet.contains(newWord) && !visited.contains(newWord)) {
                            nextSet.add(newWord);
                            visited.add(newWord);
                        }
                    }
                    chars[j] = original;
                }
            }
            
            beginSet = nextSet;
            level++;
        }
        
        return 0;
    }
}

复杂度分析

设最短路径长度为 d，分支因子为 b。

  • 单向 BFS 时间：O(b^d)
  • 双向 BFS 时间：O(b^(d/2) + b^(d/2)) = O(2 * b^(d/2)) = O(b^(d/2))

在 LeetCode 的实际用例上，双向 BFS 的时间消耗约为单向 BFS 的 1/100 到 1/10000，效果显著。

提交结果：时间击败约 98% 用户，空间击败约 75% 用户。

五、举一反三

同类题目

LeetCode 126. 单词接龙 II 返回所有最短转换序列，需要 BFS + DFS，难度大幅提升。

LeetCode 752. 打开转盘锁 类似单词接龙，4位转盘每次转动一位，找最少操作次数。同样可以用双向 BFS 优化。

LeetCode 1345. 跳跃游戏 IV 双向 BFS 在跳跃问题上的应用。

双向 BFS 模板

Set<T> beginSet = new HashSet<>(), endSet = new HashSet<>();
beginSet.add(start); endSet.add(end);
Set<T> visited = new HashSet<>();
int level = 0;

while (!beginSet.isEmpty()) {
    // 始终扩展较小的集合
    if (beginSet.size() > endSet.size()) { Set<T> tmp = beginSet; beginSet = endSet; endSet = tmp; }
    Set<T> nextSet = new HashSet<>();
    for (T node : beginSet) {
        for (T neighbor : getNeighbors(node)) {
            if (endSet.contains(neighbor)) return level + 1;
            if (!visited.contains(neighbor)) {
                nextSet.add(neighbor);
                visited.add(neighbor);
            }
        }
    }
    beginSet = nextSet;
    level++;
}
return 0;  // 不可达

六、踩坑实录

坑一：endWord 不在 wordList 中没有提前检查

如果 endWord 不在字典里，不可能到达，直接返回 0。不做这个检查，BFS 会遍历整个字典后才返回 0，浪费时间。

坑二：修改字符数组后忘记还原

chars[j] = c;
String newWord = new String(chars);
// ...
chars[j] = original;  // 必须还原！

如果不还原，下一次外层循环 j 变化时，chars 的状态是错误的。

坑三：双向 BFS 的"相遇"条件

双向 BFS 相遇是指：扩展 beginSet 时，某个新节点出现在 endSet 里（注意：是 endSet，不是 visited）。如果用 visited 判断相遇，由于两侧都往 visited 里加节点，会有误判。

坑四：双向 BFS 交换集合时，level 的计算

每次交换 beginSet 和 endSet 只是优化扩展顺序，不影响路径长度。最终 return 时是 level + 1，其中 level 是已经走过的步数（每次 beginSet 扩展完 level++），+1 是当前相遇的那一步。

坑五：beginWord 等于 endWord

题目说 beginWord != endWord，但如果边界条件没处理，当 beginWord == endWord 时，直接返回 1（只需要1个单词）。实际上题目保证不会这样，但习惯上还是要考虑。

七、总结

127 题是 BFS 优化的经典教材：从单向 BFS（可能 TLE）到双向 BFS（AC），通过减少搜索空间来提升性能。双向 BFS 的核心思想是"从两端同时搜索，总搜索量远小于单端"，在最短路径问题里是一个强力优化手段。

除了双向 BFS，这道题还可以用 A* 算法（带启发函数的 BFS）进一步优化，但实现复杂，面试里一般不做要求。

面试里提出双向 BFS 并能解释其优化原理（O(b^d) vs O(b^(d/2))），是非常强的加分项。

编辑此页
最近更新:
贡献者: xiaozhangge