LeetCode 127. 单词接龙（Word Ladder） 是一道经典的 最短路径问题，通常使用 BFS（广度优先搜索） 来解决。

🔍 题目要求

给定：

• 起始单词 beginWord
• 目标单词 endWord
• 一个单词列表 wordList

每次变换只能改变 一个字母，且变换后的单词必须在 wordList 中。

求从 beginWord 到 endWord 的 最短变换序列长度（包含首尾）。如果无法到达，返回 0。

示例：
beginWord = “hit”
endWord = “cog”
wordList = [“hot”,“dot”,“dog”,“lot”,“log”,“cog”]
输出：5 （“hit” → “hot” → “dot” → “dog” → “cog”）

🧠 解题思路：BFS（单向 or 双向）

由于要求 最短路径，BFS 天然适合。但直接对每个单词尝试所有可能的变换（如替换成 a~z）效率更高，而不是两两比较。

✅ 关键优化：

• 将 wordList 转为 Set，便于 O(1) 查找。
• 每次从队列中取出一个单词，生成其所有“一步可达”的邻居（通过替换每一位为 ‘a’~‘z’）。
• 一旦找到 endWord，立即返回当前层数（即路径长度）。
• 访问过的单词要从 set 中移除，避免重复访问（相当于 visited 标记）。

⚠️ 注意：题目要求 变换序列长度，不是边数！所以起始时 length = 1（只有 beginWord）。

✅ Java 实现（单向 BFS）

import java.util.*;

public class Solution {
public int ladderLength(String beginWord, String endWord, List wordList) {
Set wordSet = new HashSet(wordList);
if (!wordSet.contains(endWord)) {
return 0;
}

    Queue queue = new LinkedList();
    queue.offer(beginWord);
    int length = 1;

    while (!queue.isEmpty()) {
        int size = queue.size();
        for (int i = 0; i  wordList) {
Set words = new HashSet(wordList);
if (!words.contains(endWord)) return 0;

Set beginSet = new HashSet();
Set endSet = new HashSet();
beginSet.add(beginWord);
endSet.add(endWord);
int length = 1;

while (!beginSet.isEmpty() && !endSet.isEmpty()) {
    // 优化：总是扩展较小的集合
    if (beginSet.size() > endSet.size()) {
        Set tmp = beginSet;
        beginSet = endSet;
        endSet = tmp;
    }

    Set nextLevel = new HashSet();
    for (String word : beginSet) {
        char[] chars = word.toCharArray();
        for (int i = 0; i < chars.length; i++) {
            char original = chars[i];
            for (char c = 'a'; c <= 'z'; c++) {
                if (c == original) continue;
                chars[i] = c;
                String next = new String(chars);
                if (endSet.contains(next)) {
                    return length + 1;
                }
                if (words.contains(next)) {
                    nextLevel.add(next);
                    words.remove(next);
                }
            }
            chars[i] = original;
        }
    }
    beginSet = nextLevel;
    length++;
}

return 0;

}

⏱️ 复杂度分析

• 时间复杂度：O(M² × N)，其中 N 是单词数量，M 是单词长度。
  （每个单词 M 位，每位尝试 26 次，共 M×26 ≈ M，再乘以 N 个单词）
• 空间复杂度：O(N × M) 存储单词集合和队列。

✅ 总结

• 使用 BFS 找最短路径。
• 用 Set 快速查找和去重。
• 单向 BFS 足够通过 LeetCode。
• 双向 BFS 更高效，适合大数据场景。

💡 提示：本题是图论建模的经典例子——每个单词是节点，一步变换是边。

如有需要解释“为什么不能用 DFS”或“如何构建邻接表”，欢迎继续提问！