题目重点：先按变换层数找最短距离，同时记录同层多父节点，再回溯枚举所有最短词链，避免只留下第一条。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- begin/end 等长，每步恰改变一个字符，变换后的非起点单词都须在给定词典中。
- 若 begin=end 返回只含 begin 的一路径；end 不在词典返回空列表。
- 词典重复词去重，输出所有最短路径并按路径字典序排序以便稳定展示。
解题路线
- 以 begin 为 BFS 第一层，frontier 存本层所有词，dictionary 存未在更早层访问的词。
- 生成本层每词的所有合法一字符邻居，放入 next_frontier，并把当前词加入该邻居的 parents；本层全部处理完后才从 dictionary 移除 next_frontier，保留同层多条最短父边。
- 首次到达 end 的层就是最短长度；不要再扩更深层。从 end 沿 parents 回溯到 begin，反转每条路径后输出。
- 若一见 end 就立刻返回或当场删除候选词，会漏其他等长父路径。结果本身可指数多，必须把输出规模计入复杂度。
手动走一遍
hit→hot→dot→dog→cog 与 hit→hot→lot→log→cog 都为最短 5 词路径；dog、log 会在同一层各自成为 cog 的父节点。只记 visited 和一个 parent 会漏一条。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
"""Enumerate every shortest one-letter transformation path."""
from collections import defaultdict
def all_shortest_ladders(begin: str, end: str, words: list[str]) -> list[list[str]]:
if len(begin) != len(end):
return []
if begin == end:
return [[begin]]
dictionary = {word for word in words if len(word) == len(begin)}
if end not in dictionary:
return []
dictionary.discard(begin)
parents = defaultdict(set)
frontier = {begin}
letters = {character for word in dictionary | {begin, end} for character in word}
while frontier and end not in frontier:
next_frontier = set()
for word in frontier:
for index in range(len(word)):
for character in letters:
if character == word[index]:
continue
candidate = word[:index] + character + word[index + 1 :]
if candidate in dictionary:
next_frontier.add(candidate)
parents[candidate].add(word)
dictionary -= next_frontier
frontier = next_frontier
if end not in frontier:
return []
result = []
path = [end]
def backtrack(word: str) -> None:
if word == begin:
result.append(path[::-1])
return
for parent in sorted(parents[word]):
path.append(parent)
backtrack(parent)
path.pop()
backtrack(end)
return sorted(result)
复杂度
设词典 W、词长 L、可替换字符种数 A：朴素生成候选近 O(W·L²·A) 字符构造成本，父边和输出路径额外占空间；若答案有 P 条、每条长度 D，输出至少 Ω(PD)，可能指数增长。
易错点与追问
容易失分的边界
- 找到第一条路径就停止，漏同长度答案。
- 在处理本层第一个词时就删除邻居，阻止同层其他父节点记录。
- 把 Word Ladder I 的最短长度当作输出。
- Word Ladder II 只有题名却声称题目指定字符集/排序。
继续深挖
- 如果只要路径条数而非所有路径，如何 DP 计数？
- 词典百万规模时如何用 wildcard pattern 索引邻居？
- 路径数量爆炸时 API 怎样分页/限量而仍说明完整性？
