单词接龙 II

换个眼光:单词是地图上的点,差一个字母的两词之间有路。问题变成了我们熟悉的图上最短路。

光找到最短长度不够,还要能还原路径。诀窍:BFS 分层时给每个新词记下它的全部前驱(上一层谁能一步变到它)。

下面一帧一帧演:先看 BFS 怎么逐层扩散并记前驱,再看怎么沿前驱回溯拼出全部路径。

第 0 层 · 起点入队：起跑线:把 hit 入队,记它在第 0 层、已访问。灰边是「差一个字母」的潜在连接,后面 BFS 会逐条点亮真正走通的边。

扩展 hit · 找差一个字母的词：扩展 hit:词表里只有 hot 和它差一个字母(hit→hot)。hot 进入第 1 层,记 parents[hot]={hit}。

第 1 层 · hot 入层 + 记前驱：第 0 层处理完(hit 变绿表示已确定)。第 1 层只有 hot,它的前驱已记为 {hit}。这层没有 cog,继续往外扩第 2 层。

扩展 hot · 同时生出两条岔路：扩展 hot:改首字母能得到 dot(h→d)和 lot(h→l),都在词表。两条岔路同时打开——这正是后面会有两条最短路的根源。记 parents[dot]={hot}、parents[lot]={hot}。

第 2 层 · dot、lot 入层：hot 处理完变绿。第 2 层有 dot、lot 两个词,各自记好前驱。仍没碰到 cog,继续扩第 3 层。注意 BFS 同层一起推进,不偏不倚。

扩展 dot · 走向 dog：扩展 dot:改尾字母得 dog(dog)。hot 已访问、跳过。dog 进第 3 层,记 parents[dog]={dot}。

扩展 lot · 走向 log：扩展 lot:改尾字母得 log(log)。log 进第 3 层,记 parents[log]={lot}。两条岔路平行向前,都还没到终点。

第 3 层 · dog、log 入层：第 2 层全处理完(dot、lot 变绿)。第 3 层有 dog、log。它们到 cog 各差一个字母,下一层很可能命中——但纪律上仍要把这一层扩完。

扩展 dog · 命中 cog!：扩展 dog:改首字母得 cog(cog)——终点!cog 进第 4 层,记 parents[cog]={dog}。但别急着停,本层还有 log 没扩。

扩展 log · cog 多记一个前驱：扩展 log:也能一步到 cog(log→cog)。cog 已在第 4 层,所以不重复入队,只把 log 追加进 parents[cog]。现在 parents[cog]={dog, log}——两条边都通向终点。

第 4 层命中 · BFS 收工：第 4 层处理完,cog 在本层出现,最短长度锁定为 4 次变换。整张前驱图也建好了:parents 记下了每个词的所有上层来源。下面进入第二阶段——沿前驱回溯拼出所有路径。

回溯阶段 · 从 cog 倒着拼：回溯从终点 cog 起,倒着往回拼。看前驱表:parents[cog]={dog, log}——有两个来源,意味着待会儿会分裂成两条路。

回溯 · 分支一,接 dog：先走第一条分支:cog 的前驱取 dog,接到路径头部 → [dog, cog]。再查 parents[dog]={dot},只有一个来源,继续往回。

回溯 · 分支一,接 dot：继续:dog 的前驱是 dot → [dot, dog, cog]。查 parents[dot]={hot},再往回接 hot。路径一格格朝起点生长。

回溯 · 分支一,接 hot：dot 的前驱是 hot → [hot, dot, dog, cog]。查 parents[hot]={hit},而 hit 就是起点——再接一步就到头了。

回溯 · 分支一完成!：接上起点 hit,触到 beginWord,第一条最短路完工:hit→hot→dot→dog→cog。现在回到 cog 那个分叉口,走另一条分支 log。

回溯 · 分支二,接 log：回到 cog 的分叉口,这次取另一个前驱 log → [log, cog]。查 parents[log]={lot},继续往回拼。

回溯 · 分支二,接 lot：log 的前驱是 lot → [lot, log, cog]。查 parents[lot]={hot},殊途同归——又回到了 hot。

回溯 · 分支二,接 hot：lot 的前驱是 hot → [hot, lot, log, cog]。再查 parents[hot]={hit},下一步接上起点就收尾。

回溯 · 分支二完成!：接上 hit,第二条最短路也完工:hit→hot→lot→log→cog。两个分支都回到起点,回溯结束。

全部最短路 · 全景点亮：整张图看:从 hit 到 cog 共有 两条等长(4 步)的最短路,在 hot 处分叉、在 cog 处汇合。BFS 记前驱 + 回溯,把它们一条不漏地还原了出来。

易错实演 · 为何前驱要存『集合』：放大看终点 cog:dog 和 log 都能一步变到它。若 parents 只记一个父亲,回溯就只能拼出一条路,另一条凭空消失。所以前驱必须用集合/列表存全部来源。

边界三连：三个边界:终点不在词表直接返回 空;走不通也返回 空;只有一条路时回溯不分叉,自然只产出一条。

面试追问：面试三层:与 127 的差别(要不要记前驱)、双向 BFS 提速、以及用通配桶 h*t 快速建邻接——讲透就稳了。