LeetCode 题解工作台
单词接龙 II
按字典 wordList 完成从单词 beginWord 到单词 endWord 转化，一个表示此过程的 转换序列 是形式上像 beginWord -> s 1 -> s 2 -> ... -> s k 这样的单词序列，并满足： 每对相邻的单词之间仅有单个字母不同。 转换过程中的每个单词 s i （…
4
题型
3
代码语言
3
相关题
当前训练重点
困难 · 回溯·pruning
答案摘要
class Solution: def findLadders(
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 回溯·pruning 题型思路
题目描述
按字典 wordList 完成从单词 beginWord 到单词 endWord 转化，一个表示此过程的 转换序列 是形式上像 beginWord -> s1 -> s2 -> ... -> sk 这样的单词序列，并满足：
- 每对相邻的单词之间仅有单个字母不同。
- 转换过程中的每个单词
si（1 <= i <= k）必须是字典wordList中的单词。注意，beginWord不必是字典wordList中的单词。 sk == endWord
给你两个单词 beginWord 和 endWord ，以及一个字典 wordList 。请你找出并返回所有从 beginWord 到 endWord 的 最短转换序列 ，如果不存在这样的转换序列，返回一个空列表。每个序列都应该以单词列表 [beginWord, s1, s2, ..., sk] 的形式返回。
示例 1：
输入：beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"] 输出：[["hit","hot","dot","dog","cog"],["hit","hot","lot","log","cog"]] 解释：存在 2 种最短的转换序列： "hit" -> "hot" -> "dot" -> "dog" -> "cog" "hit" -> "hot" -> "lot" -> "log" -> "cog"
示例 2：
输入：beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log"] 输出：[] 解释：endWord "cog" 不在字典 wordList 中，所以不存在符合要求的转换序列。
提示：
1 <= beginWord.length <= 5endWord.length == beginWord.length1 <= wordList.length <= 500wordList[i].length == beginWord.lengthbeginWord、endWord和wordList[i]由小写英文字母组成beginWord != endWordwordList中的所有单词 互不相同
解题思路
方法一
class Solution:
def findLadders(
self, beginWord: str, endWord: str, wordList: List[str]
) -> List[List[str]]:
def dfs(path, cur):
if cur == beginWord:
ans.append(path[::-1])
return
for precursor in prev[cur]:
path.append(precursor)
dfs(path, precursor)
path.pop()
ans = []
words = set(wordList)
if endWord not in words:
return ans
words.discard(beginWord)
dist = {beginWord: 0}
prev = defaultdict(set)
q = deque([beginWord])
found = False
step = 0
while q and not found:
step += 1
for i in range(len(q), 0, -1):
p = q.popleft()
s = list(p)
for i in range(len(s)):
ch = s[i]
for j in range(26):
s[i] = chr(ord('a') + j)
t = ''.join(s)
if dist.get(t, 0) == step:
prev[t].add(p)
if t not in words:
continue
prev[t].add(p)
words.discard(t)
q.append(t)
dist[t] = step
if endWord == t:
found = True
s[i] = ch
if found:
path = [endWord]
dfs(path, endWord)
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity depends on the number of words and the branching factor at each word, with BFS and backtracking combined to explore all shortest sequences, leading to worst-case exponential growth relative to sequence length. Space complexity accounts for the BFS queue, hash tables for word lookups, and recursion stacks in backtracking, making both time and space dependent on the number of words and sequences generated, as outlined in the provided approach. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Do you handle cycles and repeated words to avoid redundant paths in backtracking?
- question_mark
Can you optimize neighbor lookups using hash tables to reduce time complexity?
- question_mark
Will you ensure that all returned sequences are the minimal length possible?
常见陷阱
外企场景- error
Failing to prune paths not on the shortest sequence, leading to TLE or incorrect extra sequences.
- error
Revisiting words within the same transformation path, causing cycles or duplicate sequences.
- error
Ignoring BFS distance levels in backtracking, which can include longer-than-necessary transformations.
进阶变体
外企场景- arrow_right_alt
Return only the count of distinct shortest transformation sequences instead of the sequences themselves.
- arrow_right_alt
Modify the problem to allow transformations that change up to two characters at a time, adjusting BFS and backtracking logic.
- arrow_right_alt
Find the shortest transformation path from beginWord to endWord while allowing intermediate words that are not in wordList if necessary.