LeetCode 题解工作台
单词接龙
字典 wordList 中从单词 beginWord 到 endWord 的 转换序列 是一个按下述规格形成的序列 beginWord -> s 1 -> s 2 -> ... -> s k ： 每一对相邻的单词只差一个字母。 对于 1 时，每个 s i 都在 wordList 中。注意， begi…
3
题型
6
代码语言
3
相关题
当前训练重点
困难 · 图·搜索
答案摘要
BFS 最小步数模型。本题可以用朴素 BFS，也可以用双向 BFS 优化搜索空间，从而提升效率。 双向 BFS 是 BFS 常见的一个优化方法，主要实现思路如下：
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 图·搜索 题型思路
题目描述
字典 wordList 中从单词 beginWord 到 endWord 的 转换序列 是一个按下述规格形成的序列 beginWord -> s1 -> s2 -> ... -> sk：
- 每一对相邻的单词只差一个字母。
- 对于
1 <= i <= k时，每个si都在wordList中。注意，beginWord不需要在wordList中。 sk == endWord
给你两个单词 beginWord 和 endWord 和一个字典 wordList ，返回 从 beginWord 到 endWord 的 最短转换序列 中的 单词数目 。如果不存在这样的转换序列，返回 0 。
示例 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" 不在字典中，所以无法进行转换。
提示：
1 <= beginWord.length <= 10endWord.length == beginWord.length1 <= wordList.length <= 5000wordList[i].length == beginWord.lengthbeginWord、endWord和wordList[i]由小写英文字母组成beginWord != endWordwordList中的所有字符串 互不相同
解题思路
方法一：BFS
BFS 最小步数模型。本题可以用朴素 BFS，也可以用双向 BFS 优化搜索空间，从而提升效率。
双向 BFS 是 BFS 常见的一个优化方法，主要实现思路如下：
- 创建两个队列 q1, q2 分别用于“起点 -> 终点”、“终点 -> 起点”两个方向的搜索；
- 创建两个哈希表 m1, m2 分别记录访问过的节点以及对应的扩展次数（步数）；
- 每次搜索时，优先选择元素数量较少的队列进行搜索扩展，如果在扩展过程中，搜索到另一个方向已经访问过的节点，说明找到了最短路径；
- 只要其中一个队列为空，说明当前方向的搜索已经进行不下去了，说明起点到终点不连通，无需继续搜索。
while q1 and q2:
if len(q1) <= len(q2):
# 优先选择较少元素的队列进行扩展
extend(m1, m2, q1)
else:
extend(m2, m1, q2)
def extend(m1, m2, q):
# 新一轮扩展
for _ in range(len(q)):
p = q.popleft()
step = m1[p]
for t in next(p):
if t in m1:
# 此前已经访问过
continue
if t in m2:
# 另一个方向已经搜索过，说明找到了一条最短的连通路径
return step + 1 + m2[t]
q.append(t)
m1[t] = step + 1
class Solution:
def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
words = set(wordList)
q = deque([beginWord])
ans = 1
while q:
ans += 1
for _ in range(len(q)):
s = q.popleft()
s = list(s)
for i in range(len(s)):
ch = s[i]
for j in range(26):
s[i] = chr(ord('a') + j)
t = ''.join(s)
if t not in words:
continue
if t == endWord:
return ans
q.append(t)
words.remove(t)
s[i] = ch
return 0
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Do you understand how BFS guarantees the shortest path in a word transformation sequence?
- question_mark
Can you explain why a hash table improves the performance of this problem?
- question_mark
Will you describe how to generate valid word transformations efficiently?
常见陷阱
外企场景- error
Not checking if `endWord` is in the `wordList` before starting the BFS, leading to unnecessary computation.
- error
Failing to track visited words properly, which can cause infinite loops or revisiting words.
- error
Misunderstanding the need to change exactly one letter at a time, which can lead to invalid transformations.
进阶变体
外企场景- arrow_right_alt
Find the shortest transformation sequence from `beginWord` to `endWord`, but with an added constraint of a maximum transformation length.
- arrow_right_alt
Extend the problem to find all shortest transformation sequences from `beginWord` to `endWord`.
- arrow_right_alt
Modify the problem to allow transformations from `beginWord` to `endWord` without the restriction of using the given word list.