单词替换

下面先把词根 cat / bat / rat 建成 Trie,看它怎么按字符分叉、在词根末尾打结束标记;再拿句子逐词去 Trie 里走。

建 Trie · 插入 cat(1/3)：从空 Trie 的根 root 出发,插入 cat 的第 1 个字符 c:根下挂出一个 c 节点(橙色是刚走到的边)。

建 Trie · 插入 cat(2/3)：沿 c 继续往下挂 a 节点(c-a 是同一条链)。蓝色是已经走过的字符边。

建 Trie · 插入 cat(3/3)：挂上 t 并在末尾打结束标记 ★(绿色)——表示 cat 是一个完整词根。一条 root→c→a→t★ 的链就建好了。

建 Trie · 再插 bat / rat：把 bat、rat 也插进来:它们各自从 root 分出一条链(c… / b… / r…),末尾都打上★。三个绿色 t★ 就是三个词根的终点。

查词 cattle · prefix=""：处理第一个有词根的单词 cattle。游标 node 站在 Trie 的 root,prefix 从空串开始,准备逐字符往下走。

cattle[0]=c · 走边 c：读 cattle[0]=c,root 下正好有 c 边,游标下行到 c 节点。c 节点没有★,还不是词根,继续。

cattle[1]=a · 走边 a：读 cattle[1]=a,c 下有 a 边,继续下行到 a。prefix="ca",a 节点仍没有★。

cattle[2]=t · 踩到 ★!：读 cattle[2]=t,走到 t 节点上有★!命中词根 cat,立刻停——后面 tle 不用再看。绿色前三格就是替换结果。

查词 the · prefix=""：再看一个没有词根的单词 the(它在 cattle 前面,这里补看一下)。游标回到 root。

the[0]=t · root 无 t 边：读 the[0]=t,可 root 下只有 c/b/r 三条边、没有 t 边!游标卡在 root 下不去,the 找不到任何词根,原样保留。

查词 rattled · prefix=""：处理 rattled。游标回到 root,prefix 清空,准备走 r 那条链。

rattled[0]=r · 走边 r：读 rattled[0]=r,root 下有 r 边,下行到 r 节点。还没★,继续。

rattled[1]=a · 走边 a：读 rattled[1]=a,r 下有 a 边,下行。prefix="ra",仍无★。

rattled[2]=t · 踩到 ★!：读 rattled[2]=t,t 节点带★!命中词根 rat,停。后面 tled 丢掉,rattled 替换成 rat。

查词 battery · prefix=""：处理最后一个有词根的单词 battery。游标回 root,走 b 那条链。

battery[0]=b · 走边 b：读 battery[0]=b,root 下有 b 边,下行到 b。无★,继续。

battery[1]=a · 走边 a：读 battery[1]=a,b 下有 a 边,下行。prefix="ba",仍无★。

battery[2]=t · 踩到 ★!：读 battery[2]=t,t 带★!命中词根 bat,停。battery 替换成 bat。

拼回句子 · 第 1~3 词：把每个词的结果按原顺序填回去:the 保留、cattle 换 cat、was 保留。绿色格子是被替换的词根。

拼回句子 · 第 4~7 词：继续填:rattled 换 rat、by 与 the 保留、battery 换 bat。三个绿色词根全部就位。

返回答案：七个词依次连成新句子,用空格拼起来返回 "the cat was rat by the bat"——cattle/rattled/battery 各自被最短词根替换,其余原样保留。

记住骨架:建 Trie + 结束标记 → 单词从 root 逐字符下行 → 走不通 break / 踩 ★ break。

边界三连：先想标准替换、找不到词根原样保留、多词根取最短三种边界,代码就稳了。

面试追问：把「Trie 为何更优」「命中即停取最短」「走不通保留原词」讲清楚,是这题面试的得分点。