哈希算法题目：单词接龙
题目描述
给定两个单词（beginWord 和 endWord）和一个字典 wordList，找到从 beginWord 到 endWord 的最短转换序列的长度。转换需遵循如下规则：
- 每次转换只能改变一个字母。
- 转换过程中的中间单词必须是字典 wordList 中的单词。
说明:
- 如果不存在这样的转换序列，返回 0。
- 所有单词具有相同的长度。
- 所有单词只由小写字母组成。
- 字典中不存在重复的单词。
- 你可以假设 beginWord 和 endWord 是非空的，且二者不相同。
示例 1:
输入:
beginWord = "hit",
endWord = "cog",
wordList = ["hot","dot","dog","lot","log","cog"]
输出: 5
解释: 一个最短转换序列是 "hit" -> "hot" -> "dot" -> "dog" -> "cog"，返回它的长度 5。
示例 2:
输入:
beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log"]
输出: 0
解释: endWord "cog" 不在字典中，所以无法转换。
解题过程（双向广度优先搜索 BFS + 哈希集合）
第一步：问题抽象与核心思路
这个问题可以看作一个在图中寻找最短路径的问题。
- 节点 (Node): 每个单词就是一个节点。
- 边 (Edge): 如果两个单词之间可以只改变一个字母相互转换，那么它们之间就存在一条无向边。
- 目标: 在由 beginWord 和 wordList 构成的图中，找到从 beginWord 节点 到 endWord 节点 的最短路径长度。
求解最短路径的典型方法是广度优先搜索 (BFS)。BFS 会从起点开始，一层层地探索所有相邻节点，第一次到达终点时的层数就是最短路径长度。
为什么用 BFS？
因为 BFS 是按“层”遍历的，最早遇到目标节点的路径，就是边数最少的路径，即最短路径。深度优先搜索 (DFS) 则可能先探索一条很长的路，效率低。
第二步：数据结构选择（哈希集合的核心作用）
为了高效地实现 BFS 和判断节点间的关系，我们需要几个关键数据结构：
- 单词集合 (
wordSet): 一个 哈希集合 (HashSet)，用于存储所有可用的单词（包括 beginWord 和 wordList）。它的作用是 O(1) 时间复杂度检查一个单词是否是“合法”的（即在字典中）。 - 已访问集合 (
visited): 一个 哈希集合，用于记录已经探索过的单词，防止走回头路，避免无限循环。 - BFS队列 (
queue): 使用队列存储当前层待探索的单词。 - 双向BFS的辅助集合 (
beginSet,endSet,nextLevelSet): 为了优化搜索，我们可以从起点和终点同时开始BFS。beginSet和endSet是哈希集合，分别存储从起点和终点出发当前层的所有节点。nextLevelSet用于暂存下一层的节点。
哈希集合的作用：提供 O(1) 的查找和添加效率，这是算法高效运行的关键。如果用列表，查找一个单词是否存在需要 O(n) 时间，算法会超时。
第三步：算法步骤详解（以双向BFS为例）
双向BFS从起点和终点同时开始搜索，当两边的搜索相遇时，就找到了最短路径。这比单向BFS通常更快。
-
初始化:
- 将
wordList转换为哈希集合wordSet，方便查找。 - 检查
endWord是否在wordSet中。如果不在，直接返回 0。 - 创建两个哈希集合：
beginSet = {beginWord},endSet = {endWord}。 - 创建已访问哈希集合
visited = {}，并将beginWord和endWord加入。 - 初始化路径长度
step = 1（因为起点本身算一步）。
- 将
-
双向BFS循环 (当
beginSet和endSet都不为空时):- 为了平衡搜索，每次我们选择较小的集合作为当前搜索的方向（
beginSet），这样可以减少搜索的分支总数。 - 创建一个新的哈希集合
nextLevelSet，用于存储从当前beginSet扩展出的下一层节点。 - 遍历当前
beginSet中的每一个单词 (currentWord)：
a. 尝试改变currentWord的每一个位置的字符（从 ‘a’ 到 ‘z’）。
b. 对于每个新生成的单词nextWord：
- 如果nextWord存在于endSet中，说明双向搜索相遇了！那么最短路径就是step + 1（从起点到当前单词的步数step，加上从当前单词到终点的那一步）。
- 如果nextWord存在于wordSet中，并且没有被访问过（不在visited中），那么它是一个合法的新节点。
- 将其加入nextLevelSet。
- 将其加入visited，标记已访问。 - 完成对当前
beginSet的遍历后，一层搜索结束。- 将
beginSet更新为nextLevelSet，准备搜索下一层。 - 路径长度
step加 1。 - 交换
beginSet和endSet的角色，保证下一轮总是从较小的集合开始扩展。
- 将
- 为了平衡搜索，每次我们选择较小的集合作为当前搜索的方向（
-
循环结束:
- 如果循环结束（某一侧的集合为空）都没有相遇，说明起点和终点之间没有通路，返回 0。
第四步：举例说明（以示例1为例）
beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]
-
初始化：
wordSet = {"hit","hot","dot","dog","lot","log","cog"}beginSet = {"hit"},endSet = {"cog"},visited = {"hit", "cog"},step = 1
-
第1轮 (从 beginSet = {"hit"} 扩展)：
nextLevelSet = {}- 处理单词 "hit":
- 改变第1位:
*it->ait, bit, cit, ...都不在 wordSet 中。 - 改变第2位:
h*t->hat, hbt, hct, ...都不在。 - 改变第3位:
hi*->hia, hib, ...遇到hot在 wordSet 中，且未访问。hot不在endSet ({"cog"})中。- 加入
nextLevelSet = {"hot"}，visited = {"hit","cog","hot"}
- 改变第1位:
- 本轮结束。
beginSet更新为{"hot"}，step = 2。交换后，beginSet = {"hot"},endSet = {"cog"}。
-
第2轮 (从 beginSet = {"hot"} 扩展)：
nextLevelSet = {}- 处理单词 "hot":
- 生成邻居：
*ot-> 找到dot,lot在 wordSet 中，且未访问。- 都不在
endSet中。 - 加入
nextLevelSet = {"dot", "lot"}，visited加入这两个词。
- 都不在
- 生成邻居：
- 本轮结束。
beginSet = {"dot", "lot"},step = 3。交换后，beginSet = {"dot", "lot"},endSet = {"cog"}。
-
第3轮 (从 beginSet = {"dot", "lot"} 扩展)：
- 我们选择从较小的集合扩展的逻辑在这里体现。此时
beginSet有2个元素，endSet有1个元素。算法会先交换，让beginSet = {"cog"},endSet = {"dot", "lot"}。但为了理解，我们按不交换的顺序看逻辑： - 处理 "dot"：邻居有
dog(未访问)。 - 处理 "lot"：邻居有
log(未访问)。 nextLevelSet = {"dog", "log"},step = 4。交换后，beginSet = {"dog", "log"},endSet = {"cog"}。
- 我们选择从较小的集合扩展的逻辑在这里体现。此时
-
第4轮 (从 beginSet = {"dog", "log"} 扩展)：
- 处理 "dog"：邻居有
cog。cog在endSet中！ 搜索相遇！- 返回
step + 1 = 4 + 1 = 5。
- 处理 "dog"：邻居有
第五步：复杂度分析
- 时间复杂度：O(N * L * 26)。N 是单词列表中的单词数量，L 是单词的长度。最坏情况下，每个单词都需要生成 L * 26 个邻居变体，每个变体的查找在哈希集合中是 O(1)。
- 空间复杂度：O(N)。主要用于存储哈希集合
wordSet，visited以及 BFS 队列/集合。
核心要点：本题巧妙地将字典转换为哈希集合，使得邻居查找操作极为高效。双向BFS进一步优化了搜索空间，是解决此类单词接龙/图最短路径问题的经典模式。