单词替换

下面 16 步动画会按主解代码推进，而不是泛泛讲题型。

1. 把词根装进集合：先把词典 ["cat","bat","rat"] 放进集合 roots，方便 O(1) 判断某个前缀是不是词根。答案列表 ans 初始为空 []。

2. 取第 1 个单词 cattle：把句子按空格拆成 [cattle, was, battery]，先处理第 1 个单词 cattle。前缀 prefix 从空串 "" 开始，逐个字符往后加。

3. 加第 1 个字符 c：把 cattle[0]=c 接到 prefix 后面，prefix 变成 "c"。接着检查 "c" 在不在 roots 里。

4. 检查 c 是否为词根："c" 不在 roots={cat,bat,rat} 中，没命中词根，继续往后加字符。

5. 加第 2 个字符 a：把 cattle[1]=a 接上，prefix 变成 "ca"。再检查 "ca" 是不是词根。

6. 检查 ca 是否为词根："ca" 也不在 roots 中，仍未命中，继续往后加。

7. 加第 3 个字符 t：把 cattle[2]=t 接上，prefix 变成 "cat"。这次检查 "cat" 是不是词根。

8. 命中词根 cat："cat" 在 roots 中，命中最短词根！立刻 break——后面的 tle 不用再看。把 cat 加进 ans，ans=[cat]。绿色高亮的前三个字符就是替换结果。

9. 取第 2 个单词 was：处理第 2 个单词 was，重新把 prefix 清回空串 ""，照样逐字符加。ans 当前是 [cat]。

10. 加 w，检查：prefix 加到 "w"，不在 roots 中，继续。

11. 加 wa、was，都不命中：prefix 依次走到 "wa"、"was" 都不在 roots 中。整个单词找不到词根，was 保持原样，ans=[cat, was]。

12. 取第 3 个单词 battery：处理最后一个单词 battery，prefix 重置为空串 ""。ans 当前是 [cat, was]。

13. 加 b，检查：prefix 加到 "b"，不在 roots 中，继续往后加。

14. 加 a，检查 ba：prefix 加到 "ba"，还不在 roots 中，再加一个字符。

15. 加 t，命中词根 bat：prefix="bat" 在 roots 中，命中！break，后面 tery 不再看。把 bat 加进 ans，ans=[cat, was, bat]。绿色三字符即替换结果。

16. 拼接答案，返回：三个单词都处理完，ans=[cat, was, bat]：cattle→cat、was 不变、battery→bat。用空格把它们拼起来，返回 "cat was bat"，就是最终答案。

记住这题的代码骨架：题意约束先落到状态变量，再用循环或递归维护它。