LeetCode 127. 单词接龙
字数 1699 2025-11-03 08:34:44
LeetCode 127. 单词接龙
题目描述
给定两个单词（beginWord 和 endWord）和一个字典 wordList，找到从 beginWord 到 endWord 的最短转换序列的长度。转换需遵循如下规则：
- 每次转换只能改变一个字母。
- 转换过程中的中间单词必须是字典 wordList 中的单词。
说明:
- 如果不存在这样的转换序列，返回 0。
- 所有单词具有相同的长度。
- 所有单词只由小写字母组成。
- 字典中不存在重复的单词。
- 你可以假设 beginWord 和 endWord 是非空的，且二者不相同。
示例：
beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]
最短序列是 "hit" -> "hot" -> "dot" -> "dog" -> "cog"，返回长度 5。
解题过程
1. 问题分析
此题可抽象为图论中的最短路径问题：
- 每个单词是一个节点。
- 如果两个单词只有一个字母不同，则它们之间有一条无向边。
- 目标是找到从 beginWord 节点到 endWord 节点的最短路径（边数）。
2. 核心思路：广度优先搜索（BFS）
BFS 能按层遍历节点，首次遇到 endWord 时所在的层数即为最短路径长度。步骤：
- 队列存储当前层的单词。
- 用一个集合记录已访问的单词，避免重复处理。
- 逐层扩展：对每个单词，生成所有可能的下一个单词（只差一个字母），若在 wordList 中且未访问，则加入下一层。
3. 优化单词变换检查
直接比较每个单词与其他所有单词的差异会超时。高效方法：对当前单词的每个位置，依次替换为 26 个字母，生成新单词，检查是否在 wordList 中。
例如："hit" 变换第一位：生成 "ait", "bit", ..., "zit"（排除 "hit"本身），检查这些单词是否在字典中。
4. 算法步骤
- 将 wordList 转为哈希集合，方便 O(1) 查询。
- 若 endWord 不在集合中，直接返回 0。
- 初始化队列（加入 beginWord）和已访问集合（加入 beginWord），路径长度初始为 1（beginWord 自身算一层）。
- 当队列非空时：
- 当前层节点数 = 队列大小。
- 遍历当前层每个单词：
- 若该单词等于 endWord，返回当前路径长度。
- 否则，生成所有可能的下一个单词：
- 遍历单词的每个位置。
- 对该位置尝试 26 个字母替换，生成新单词。
- 若新单词在 wordList 中且未访问，加入队列和已访问集合。
- 当前层处理完后，路径长度 +1。
- 队列空仍未找到 endWord，返回 0。
5. 复杂度分析
- 时间：单词长度 L，单词数 N。最坏情况下检查所有单词，每个单词生成 26L 个新单词，总 O(L × N × 26)。
- 空间：O(N) 存储队列和已访问集合。
示例演示
beginWord="hit", endWord="cog", wordList=["hot","dot","dog","lot","log","cog"]
- 初始：队列=["hit"]，长度=1。
- 处理"hit"：生成"it"（如"ait"）、"ht"（如"hat"）、"hi*"（如"hia"）等，只有"hot"在字典中。队列变为["hot"]，长度=2。
- 处理"hot"：生成"ot"（得"dot","lot"）、"ht"（无）、"ho*"（无）。队列变为["dot","lot"]，长度=3。
- 处理"dot"：生成"ot"（无）、"dt"（无）、"do*"（得"dog"）。队列变为["lot","dog"]。
- 处理"lot"：生成"ot"（无）、"lt"（无）、"lo*"（得"log"）。队列变为["dog","log"]，长度=4。
- 处理"dog"：生成"*og"（得"cog"），找到 endWord，返回长度=5。
此过程确保最短路径被优先找到。