题目重点：求字典内逐步替换一个字符的最短词链，构造通配桶避免每次比较全部单词。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 训练非空同长度ASCII小写词，每步只替换一个字符，结果计链中词数；end必须在字典，重复词去重。begin=end也仍按end存在前提判断。
- begin可不在字典，作为起点加入；无路径返回0，不要求所有最短词链。
解题路线
- 构造每词L个pattern，例如hot→*ot/h*t/ho*。同pattern词之间只差该位置，因此可作为无权图邻居。*不属于输入字符，避免与真实字符混淆。
- BFS保存(word,distance)且入队即seen，第一次遇end的distance为最短词数。起点距离1，不是边数0。
- 某pattern第一次被扫描时把其中未见词都入队，随后删除该bucket；所有这些词此时被最早可达层触及，后续单源BFS再扫不会产生更短发现，因此无需反复遍历大桶。
- bucket删除适用于只求一次最短长度；若要所有最短路径，需要同层多父记录，不能直接沿用永久删除后假定保留所有路径。双向BFS也需要独立frontier/visited与停止证明。
- 输入校验长度和字符，end缺失提前0。词列表大时不要为每个被出队词做O(NL)全字典比较；bucket预处理换取额外空间。
手动走一遍
hit→hot→dot→dog→cog得到5，字典可为hot/dot/dog/lot/log/cog。没有cog则0；若begin=end且字典含该词返回1。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
from collections import deque
def ladder_length(begin,end,words):
"""Same-length lowercase ASCII words, one substitution; length counts words.
end must be in dictionary even when begin==end. Duplicate entries deduped.
"""
length=len(begin)
if len(end)!=length or any(len(w)!=length for w in words):raise ValueError('dimension mismatch')
if any(not w or any(not 'a'<=c<='z' for c in w) for w in [begin,end,*words]):
raise ValueError('nonempty lowercase ASCII words')
dictionary=set(words)
if end not in dictionary:return 0
dictionary.add(begin);buckets={}
for word in dictionary:
for i in range(length):
pattern=word[:i]+'*'+word[i+1:];buckets.setdefault(pattern,[]).append(word)
queue=deque([(begin,1)]);seen={begin}
while queue:
word,distance=queue.popleft()
if word==end:return distance
for i in range(length):
pattern=word[:i]+'*'+word[i+1:]
for neighbor in buckets.pop(pattern,[]):
if neighbor not in seen:
seen.add(neighbor);queue.append((neighbor,distance+1))
return 0
复杂度
Python创建pattern切片长度L，因此预处理O(NL²)时间、存储字符串pattern最坏O(NL²)字节加O(NL)桶引用。BFS每桶只遍历一次O(NL)邻接引用，但生成pattern仍O(NL²)；不能忽略Python切片而直接标O(NL)。
易错点与追问
容易失分的边界
- visited出队才设置会在同层重复入队多个相同词。
- 返回边数与题目词数少1。
- 求所有最短路径时只留单父或提前删桶会漏等长分支。
继续深挖
- 若字母表很小，直接每位置试26字符查set与pattern桶如何比较？
- 要返回一条路径时，parent应在何时设置避免覆盖最短发现？
