知序
返回
保存草稿
发布
H1
H2
H3
1
2
3
Excalidraw 图
AI 写作
AI 优化
目录
输入内容后显示目录
Markdown
# 102 - 单词接龙 ## 题目(LeetCode 127) 给定两个单词 `beginWord` 和 `endWord`,以及一个字典 `wordList`。 每次只能改变一个字母,且变换后的单词必须在 `wordList` 中。 求从 `beginWord` 到 `endWord` 的**最短转换序列**中的单词数。如果不存在,返回 0。 ``` 输入:beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"] 输出:5 解释:hit → hot → dot → dog → cog 输入:beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log"] 输出:0 解释:cog 不在 wordList 中 ``` ## 核心思路:无向图 BFS ``` 每个单词是一个节点 两个单词相差一个字母 → 之间存在一条边 问题转化为:无权图中两节点间的最短路径 → BFS hit │ hot / \ dot lot │ │ dog log \ / cog ``` --- ## 解法一:BFS + 枚举变种(推荐) ### 关键优化 ``` 传统方法:对每个单词,遍历 wordList 找"差一个字母的词" → O(N² × L),N 个单词每轮遍历 N 个,每个比较 L 个字母 优化方法:对每个单词的每个位置,枚举 26 个字母生成新词 → 固定 O(26 × L),与 wordList 大小无关! → 第 i 位从 'a' 到 'z' 替换,生成所有可能的新词,查 Set 存在性 ``` ```java class Solution { public int ladderLength(String beginWord, String endWord, List<String> wordList) { // 1. wordList 转 Set,O(1) 查找 Set<String> wordSet = new HashSet<>(wordList); if (!wordSet.contains(endWord)) return 0; // 2. BFS 初始化 Queue<String> queue = new LinkedList<>(); queue.offer(beginWord); Set<String> visited = new HashSet<>(); visited.add(beginWord); int step = 1; // 层数(包含 beginWord) while (!queue.isEmpty()) { int size = queue.size(); for (int i = 0; i < size; i++) { String word = queue.poll(); // 到达目标 if (word.equals(endWord)) return step; // 生成所有相邻单词(变一个字母) char[] chars = word.toCharArray(); for (int j = 0; j < chars.length; j++) { char old = chars[j]; for (char c = 'a'; c <= 'z'; c++) { if (c == old) continue; chars[j] = c; String next = new String(chars); if (wordSet.contains(next) && !visited.contains(next)) { visited.add(next); queue.offer(next); } } chars[j] = old; // 恢复 } } step++; // 一层结束 } return 0; // 无法到达 } } ``` ### 执行过程模拟 ``` beginWord = "hit", endWord = "cog" wordList = ["hot","dot","dog","lot","log","cog"] 队列: [hit] step=1 出队 hit, 枚举: hit → *it: ait,bit,...,zit → 无匹配 hit → h*t: hat,hbt,...,hzt → hot ✓ (入队) hit → hi*: hia,hib,...,hiz → 无匹配 队列: [hot] step=2 出队 hot, 枚举: hot → *ot: aot,bot,...,zot → dot ✓, lot ✓ (入队) hot → h*t: 略 hot → ho*: 略 队列: [dot, lot] step=3 出队 dot, 枚举: dot → *ot: cot ✓ (入队) → 包含 endWord! dot → d*t: 略 dot → do*: dog ✓ (入队) 队列: [lot, cot, dog] step=4 出队 lot: 枚举相邻 → log ✓ (入队) 队列: [cot, dog, log] step=4 出队 cot: 枚举... 出队 dog, 枚举 → cog ✓ = endWord! return step=5 路径: hit(1) → hot(2) → dot(3) → dog(4) → cog(5) ✓ ``` --- ## 解法二:双向 BFS(更快) ``` 同时从 beginWord 和 endWord 出发 BFS 当两边"相遇"时 → 找到最短路径 图示: hit → hot → dot ──┐ ├─→ 相遇! cog → dog ────────┘ 复杂度:从 O(b^d) 降到 O(b^(d/2)),b = 分支因子 ``` ```java class Solution { public int ladderLength(String beginWord, String endWord, List<String> wordList) { Set<String> wordSet = new HashSet<>(wordList); if (!wordSet.contains(endWord)) return 0; // 两个方向:begin → end, end → begin Set<String> beginSet = new HashSet<>(); Set<String> endSet = new HashSet<>(); Set<String> visited = new HashSet<>(); beginSet.add(beginWord); endSet.add(endWord); int step = 1; // 已包含首尾单词 while (!beginSet.isEmpty() && !endSet.isEmpty()) { // 每次扩展较小的集合(优化:谁能扩散到新节点谁就是 beginSet) if (beginSet.size() > endSet.size()) { Set<String> tmp = beginSet; beginSet = endSet; endSet = tmp; } Set<String> nextSet = new HashSet<>(); for (String word : beginSet) { char[] chars = word.toCharArray(); for (int i = 0; i < chars.length; i++) { char old = chars[i]; for (char c = 'a'; c <= 'z'; c++) { chars[i] = c; String next = new String(chars); // 相遇!两个方向在中间碰头 if (endSet.contains(next)) return step + 1; if (wordSet.contains(next) && !visited.contains(next)) { visited.add(next); nextSet.add(next); } } chars[i] = old; } } beginSet = nextSet; step++; } return 0; } } ``` --- ## 解法三:BFS + 通配符建图(预处理) ``` 把所有单词按 "h*t"、"*ot" 这样的通配符分组 hit → 通配符 h*t、hi*、*it hot → 通配符 h*t、ho*、*ot ← 与 hit 共享 h*t → 相邻! 预处理后,查找相邻单词不用 26 次枚举,而是直接查通配符分组。 ``` ```java class Solution { public int ladderLength(String beginWord, String endWord, List<String> wordList) { Set<String> wordSet = new HashSet<>(wordList); if (!wordSet.contains(endWord)) return 0; // 通配符 → 单词列表 Map<String, List<String>> patternMap = new HashMap<>(); // 把 beginWord 也纳入建图 wordSet.add(beginWord); for (String word : wordSet) { char[] chars = word.toCharArray(); for (int i = 0; i < chars.length; i++) { char old = chars[i]; chars[i] = '*'; String pattern = new String(chars); patternMap.computeIfAbsent(pattern, k -> new ArrayList<>()).add(word); chars[i] = old; } } // BFS Queue<String> queue = new LinkedList<>(); Set<String> visited = new HashSet<>(); queue.offer(beginWord); visited.add(beginWord); int step = 1; while (!queue.isEmpty()) { int size = queue.size(); for (int k = 0; k < size; k++) { String word = queue.poll(); if (word.equals(endWord)) return step; // 通过该单词的所有通配符找到相邻单词 char[] chars = word.toCharArray(); for (int i = 0; i < chars.length; i++) { char old = chars[i]; chars[i] = '*'; String pattern = new String(chars); for (String neighbor : patternMap.getOrDefault(pattern, Collections.emptyList())) { if (!visited.contains(neighbor)) { visited.add(neighbor); queue.offer(neighbor); } } chars[i] = old; } } step++; } return 0; } } ``` --- ## 复杂度对比 | 解法 | 时间 | 空间 | 适用 | |------|------|------|------| | **枚举 26 字母** | O(N × L² × 26) | O(N × L) | 通用,wordList 大时最优 | | **双向 BFS** | O(b^(d/2)) | O(N × L) | d 很大时显著提速 | | **通配符建图** | O(N × L) 建图 + BFS | O(N × L) | N 小 L 大时优于枚举 | > N = wordList 长度,L = 单词长度,b = 平均分支,d = 最短路径长度 --- ## 边界与细节 ```java // 1. beginWord 可能不在 wordList 中(允许的,题设如此) // 2. endWord 不在 wordList → 直接返回 0 // 3. 所有单词长度相同(题设约束) // 4. 返回的是"单词个数"而非"步数" // hit → hot → cog:返回 3,改变了 2 次(路径上共 3 个单词) ``` --- ## 一句话总结 无权图最短路径 → BFS。枚举 26 个字母比遍历 wordList 更高效(O(26L) vs O(NL)),双向 BFS 进一步将搜索空间减半。返回的是路径上的单词数(包含首尾),不是转换步数。 --- ## 延伸 **Q:如果要求输出所有最短路径,怎么改?(LeetCode 126)** A:BFS 找到最短距离后,DFS 回溯找路径。关键是记录每个单词在 BFS 第几层被访问,DFS 时只往"下一层"走,避免死循环。 --- ## 同类题目 | 题目 | 描述 | |------|------| | LeetCode 126 | 单词接龙 II — 输出所有最短路径 | | LeetCode 433 | 最小基因变化 — 本质上同题 | | LeetCode 752 | 打开转盘锁 — BFS 变种,带锁死状态 | --- 上一篇:[101 - 小于n的最大数字](file:///f:/KiroPro/Text/java/101-max-number-less-than-n.md)
预览
发布文章
添加摘要让读者更快了解文章内容
取消
确认发布
AI 写作助手
输入一个主题,AI 将为你生成一篇 Markdown 博客文章
AI 正在写作中...
取消
开始生成
AI 优化助手
描述你的修改需求,AI 将在原文基础上进行补充或微调
AI 正在优化中...
取消
开始优化
画布
从已有图里选
✕
图名
保存后生成 /images/excalidraw/<图名>.svg(只能用字母、数字、短横线、下划线、点)
取消
保存并插入