哈希算法题目：单词接龙

题目描述

给你两个单词 beginWord 和 endWord，以及一个单词列表 wordList。需要找出从 beginWord 到 endWord 的最短转换序列的长度。转换规则如下：

1. 每次只能转换一个字母。
2. 转换过程中的每个单词都必须是 wordList 中的单词（endWord 也必须在 wordList 中）。
3. 如果无法完成转换，则返回 0。

示例：
输入：beginWord = “hit”, endWord = “cog”, wordList = [“hot”,”dot”,”dog”,”lot”,”log”,”cog”]
输出：5
解释：最短转换序列是 “hit” -> “hot” -> “dot” -> “dog” -> “cog”，长度为 5。

解题思路

我们可以把每个单词看作图中的一个节点。如果两个单词之间只有一个字母不同，那么它们之间就存在一条无向边。这样，问题就转化为了在无向图中，求从起点节点（beginWord）到终点节点（endWord）的最短路径问题。对于最短路径问题，广度优先搜索（BFS） 是最合适的方法，因为它会按层探索，首次遇到目标节点时的路径长度就是最短的。

哈希表在这个问题中扮演着关键角色：

1. 快速查找与去重：我们需要快速判断一个单词是否在 wordList 中，以及是否已经被访问过，使用 HashSet 可以实现 O(1) 时间复杂度的查找。
2. 虚拟节点优化（核心技巧）：直接比较任意两个单词是否只差一个字母需要 O(L) 时间（L 为单词长度），如果对每个单词都和其余单词比较，会非常慢（O(N²L)）。我们可以为每个单词创建 L 个“虚拟节点”。例如单词 “hot”，它的三个虚拟节点是：*ot, h*t, ho*。那么，所有能通过变换一个字母得到的单词（如 “dot”, “lot”）都会共享同一个虚拟节点。这样，我们只需要为当前单词生成所有虚拟节点，然后查找哪些真实单词也对应这些虚拟节点，即可快速找到下一层的节点。管理“单词到其虚拟节点列表”以及“虚拟节点到对应单词列表”的关系，使用哈希表（HashMap）是最佳选择。

循序渐进讲解

第 1 步：基础检查与数据结构准备

首先进行边界条件检查，并初始化几个核心的哈希集合/映射。

// 1. 将单词列表转换为哈希集合，方便快速查找和去重
Set<String> wordSet = new HashSet<>(wordList);
if (!wordSet.contains(endWord)) {
    return 0; // 终点不在列表中，无法转换
}
// 移除起点，避免重复处理（如果它在列表中的话）
wordSet.remove(beginWord);

// 2. 使用队列进行BFS
Queue<String> queue = new LinkedList<>();
queue.offer(beginWord);

// 3. 记录已访问过的单词和其对应的路径长度（层次）
Map<String, Integer> visited = new HashMap<>();
visited.put(beginWord, 1);

第 2 步：构建虚拟节点的映射关系（预处理）

这是优化性能的关键一步。我们为 wordList 中的每个单词（包括 beginWord 和 endWord）构建其所有可能的虚拟模式，并建立从“虚拟模式”到“所有能匹配该模式的真实单词”的映射。

// key: 虚拟模式，如 “*ot”
// value: 能匹配这个模式的所有真实单词列表，如 [“hot”, “dot”, “lot”]
Map<String, List<String>> patternToWords = new HashMap<>();

for (String word : wordList) {
    for (int i = 0; i < word.length(); i++) {
        // 生成第i个字符被替换为‘*’的模式
        String pattern = word.substring(0, i) + "*" + word.substring(i + 1);
        // 将该单词加入该模式对应的列表中
        patternToWords.computeIfAbsent(pattern, k -> new ArrayList<>()).add(word);
    }
}
// 注意：beginWord 也需要加入这个映射，因为转换可能从它开始
for (int i = 0; i < beginWord.length(); i++) {
    String pattern = beginWord.substring(0, i) + "*" + beginWord.substring(i + 1);
    patternToWords.computeIfAbsent(pattern, k -> new ArrayList<>()).add(beginWord);
}

第 3 步：执行广度优先搜索（BFS）

BFS 会逐层探索，每深入一层，路径长度（即转换序列长度）加 1。

while (!queue.isEmpty()) {
    String currentWord = queue.poll();
    int currentLevel = visited.get(currentWord); // 当前单词所在的层次（路径长度）

    // 遍历当前单词的每一个字符位置，生成所有可能的虚拟模式
    for (int i = 0; i < currentWord.length(); i++) {
        String pattern = currentWord.substring(0, i) + "*" + currentWord.substring(i + 1);

        // 通过哈希表，快速获取所有与当前单词“相邻”（差一个字母）的单词
        for (String neighbor : patternToWords.getOrDefault(pattern, new ArrayList<>())) {
            // 如果邻居就是终点，直接返回结果（当前层数+1）
            if (neighbor.equals(endWord)) {
                return currentLevel + 1;
            }
            // 如果这个邻居单词没有被访问过，且存在于单词集中
            if (!visited.containsKey(neighbor) && wordSet.contains(neighbor)) {
                // 标记为已访问，并记录其层次
                visited.put(neighbor, currentLevel + 1);
                // 将其加入队列，以便下一层探索
                queue.offer(neighbor);
            }
        }
    }
}

第 4 步：返回结果

如果 BFS 结束都没有遇到 endWord，说明不存在转换序列。

return 0; // 无法到达终点

算法复杂度分析

• 时间复杂度：O(N * L²)。其中 N 是单词列表中的单词数量，L 是每个单词的长度。主要开销在于：1) 构建模式映射 O(N * L)；2) BFS 过程中，每个单词会被处理一次，每次处理需要生成 L 个模式，并通过哈希表 O(L) 时间获取邻居（因为构建映射时，每个单词的每个模式都对应一个列表，获取列表是 O(1)，但遍历列表中的单词是 O(N) 的潜在风险？实际上，由于每个单词只被访问一次，且每条边（虚拟节点连接的单词对）也只会被遍历一次，总操作数与边数成正比，最坏情况下为 O(N²L)。但使用虚拟节点后，平均情况远好于直接的逐对比较。
• 空间复杂度：O(N * L)。存储模式映射需要 O(N * L) 的空间（每个单词有 L 个模式），BFS 队列和访问记录需要 O(N) 的空间。

关键点总结

1. 问题转化：将单词转换问题抽象为无向图的最短路径问题。
2. 核心算法：使用 BFS 来保证找到的路径是最短的。
3. 哈希表的妙用：
   • HashSet (wordSet) 用于 O(1) 时间判断单词有效性。
   • HashMap (visited) 用于记录访问状态和路径长度。
   • HashMap (patternToWords) 是性能优化的核心，它通过“虚拟节点”的概念，将寻找邻居的操作从 O(N*L) 降到了 O(L)。我们不再需要比较当前单词和列表中的所有其他单词，而是直接通过其虚拟模式找到所有可能的下一跳。

这种方法高效地解决了“单词接龙”问题，是图论 BFS 与哈希表数据结构结合的经典应用。