127. 单词接龙：双向 BFS 最短路.md

题目简述：

字典 wordList 中从单词 beginWord 到 endWord 的 转换序列 是一个按下述规格形成的序列 beginWord -> s1 -> s2 -> ... -> sk：

• 每一对相邻的单词只差一个字母。
• 对于 1 <= i <= k 时，每个 si 都在 wordList 中。注意， beginWord 不需要在 wordList 中。
• sk == endWord

给你两个单词 beginWord 和 endWord 和一个字典 wordList ，返回 从 beginWord 到 endWord 的 最短转换序列 中的 单词数目 。如果不存在这样的转换序列，返回 0 。

题目链接：127. 单词接龙

思路

显然这是一个无向图的最短路问题，考虑 BFS。

单向 BFS 最短路已然堪用，为了加快算法求解速度，我们可以考虑双向 BFS，即从起点 beginWord 与终点 endWord 同时出发。

代码

不考虑邻接表建表成本的情况下，BFS 的时间复杂度为 $O(N+E)$，空间复杂度为 $O(E)$。这里 $O(E)$ 为邻接表的空间开销，最坏为 $O(NL)$，其中 $L$ 为最长的字符串长度。

暴力遍历建邻接表的时间开销为 $O(N^2L)$，对于 BFS 的 $O(N+E)$ 时间复杂度而言这是一笔巨额开销。改为通配符桶建表可以大大节省时间开销。或者，不建完整的邻接表、只在寻找邻居时暴力遍历寻找长度相等、编辑距离为 1 且位于 wordList 中的元素，这样也能在相当程度上避免暴力遍历建邻接表带来的不菲开销。

class Solution {

    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        Map<String, List<String>> adj = adjacency(beginWord, wordList);
        if (!adj.containsKey(endWord)) return 0;

        Set<String> used1 = new HashSet<>(List.of(beginWord));
        Set<String> used2 = new HashSet<>(List.of(endWord));
        Deque<String> queue1 = new ArrayDeque<>(List.of(beginWord));
        Deque<String> queue2 = new ArrayDeque<>(List.of(endWord));
        int layerSize1 = 1;  // 每轮 BFS 起始时队列长度
        int layerSize2 = 1;
        int order1 = 0;      // BFS 轮数
        int order2 = 0;
        
        while (!queue1.isEmpty() || !queue2.isEmpty()) {
            while (layerSize1 > 0) {
                String s = queue1.poll();
                layerSize1--;
                for (String next : adj.get(s)) {
                    if (used1.contains(next)) continue;
                    if (used2.contains(next)) {
                        return order1 + order2 + 2;
                    } else {
                        used1.add(next);
                        queue1.offer(next);
                    }
                }
            }
            layerSize1 = queue1.size();
            if (layerSize1 > 0) order1++;

            while (layerSize2 > 0) {
                String s = queue2.poll();
                layerSize2--;
                for (String next : adj.get(s)) {
                    if (used2.contains(next)) continue;
                    if (used1.contains(next)) {
                        return order1 + order2 + 2;
                    } else {
                        used2.add(next);
                        queue2.offer(next);
                    }
                }
            }
            layerSize2 = queue2.size();
            if (layerSize2 > 0) order2++;
        }

        return 0;
    }

    // 使用通配符桶可以以更低的时间复杂度构建邻接表，这里简便起见暴力遍历
    private Map<String, List<String>> adjacency(String beginWord, List<String> wordList) {
        wordList.addLast(beginWord);
        Map<String, List<String>> map = new HashMap<>();
        for (String s : wordList) map.put(s, new ArrayList<>());

        for (String s : wordList) {
            List<String> list = map.get(s);
            for (String ss : wordList) {
                // if (s.length() != ss.length()) continue;
                int diff = 0;
                for (int i = 0; i < s.length(); i++) {
                    if (s.charAt(i) != ss.charAt(i)) {
                        diff++;
                        if (diff > 1) continue;
                    }
                }
                if (diff == 1) {
                    list.add(ss);
                }
            }
        }

        wordList.removeLast();
        return map;
    }
}

下面是 GPT 5 - thinking 给出的通配符桶建邻接表的代码，可以直接替换上文中的 adjacency()：

private Map<String, List<String>> adjacency(String beginWord, List<String> wordList) {
    int L = beginWord.length();

    // 1) 只保留同长度单词，并保证包含 beginWord；不要修改入参
    List<String> words = new ArrayList<>(wordList.size() + 1);
    for (String w : wordList) if (w.length() == L) words.add(w);
    if (!words.contains(beginWord)) words.add(beginWord);

    // 2) 初始化邻接表（用 Set 去重，最后转 List）
    Map<String, Set<String>> adjSet = new HashMap<>();
    for (String w : words) adjSet.put(w, new HashSet<>());

    // 3) 建桶：pattern -> list of words
    Map<String, List<String>> bucket = new HashMap<>(words.size() * L * 2);
    for (String w : words) {
        for (int i = 0; i < L; i++) {
            String key = w.substring(0, i) + '*' + w.substring(i + 1);
            bucket.computeIfAbsent(key, k -> new ArrayList<>()).add(w);
        }
    }

    // 4) 按桶连边：同桶内两两相邻
    for (List<String> list : bucket.values()) {
        int k = list.size();
        for (int i = 0; i < k; i++) {
            String a = list.get(i);
            Set<String> neiA = adjSet.get(a);
            for (int j = 0; j < k; j++) {
                if (i == j) continue;
                neiA.add(list.get(j));
            }
        }
    }

    // 5) 转回 Map<String, List<String>>
    Map<String, List<String>> adj = new HashMap<>(adjSet.size() * 2);
    for (Map.Entry<String, Set<String>> e : adjSet.entrySet()) {
        adj.put(e.getKey(), new ArrayList<>(e.getValue()));
    }
    return adj;
}