如何用 Trie 做词根替换（Replace Words）？

简化版

把词根字典建成 Trie。处理句子里的每个单词时，从左到右沿 Trie 查找，一旦遇到 isEnd=true 的节点，就用当前前缀替换整个单词；如果中途走不通，就保留原词。

详细版

词根替换的关键是“找最短词根前缀”。Trie 能逐字符匹配单词前缀，并在最早的词根终止节点停止。

步骤：

将所有词根插入 Trie，终止节点标记 isEnd=true。
对句子按空格拆成单词。
对每个单词，从根开始逐字符走 Trie。
若某一步孩子不存在，说明没有词根可替换，返回原词。
若走到 isEnd=true，返回当前前缀，因为题目要求最短词根。

String findRoot(String word) {
    Trie node = root;
    StringBuilder prefix = new StringBuilder();
    for (char ch : word.toCharArray()) {
        int i = ch - 'a';
        if (node.children[i] == null) return word;
        node = node.children[i];
        prefix.append(ch);
        if (node.isEnd) return prefix.toString();
    }
    return word;
}

构建 Trie 的时间是所有词根总长度，替换句子的时间是所有单词长度之和，遇到短词根还能提前停止。

完整版教学

一、题目本质：找最短可用前缀

词根替换不是找任意前缀，而是找最短词根。比如词根字典有 cat 和 cattle，单词是 cattleman，应该替换成 cat，因为 cat 已经是词根且更短。这个“最短命中立即停止”的规则非常适合 Trie。

如果用哈希表，也可以枚举单词的所有前缀：c、ca、cat，每个去哈希表查。但 Trie 不需要反复创建前缀字符串，也能在某个字符走不通时提前停止。两者都能做，Trie 的前缀语义更自然。

dictionary = [cat, bat, rat]
sentence   = "the cattle was rattled by the battery"
result     = "the cat was rat by the bat"

二、为什么遇到 isEnd 就立刻返回

Trie 中一个节点的 isEnd=true 表示从根到该节点构成一个完整词根。由于我们从单词第一个字符开始向后走，第一次遇到 isEnd 的位置，一定是最短词根。继续往下找只会得到更长词根，不符合题意。

Trie contains:
root -> c -> a -> t(isEnd) -> t -> l -> e(isEnd)

word = cattleman
走到 cat 时已命中最短词根，返回 cat
不应该继续返回 cattle

这也是 search 和“词根匹配”的差异：普通 search 要走完整个 word 后看 isEnd；词根替换只要前缀节点命中 isEnd 就能停。

三、用数字例子比较 Trie 和枚举前缀

假设句子里有 100000 个单词，平均长度 20，词根最大长度 5。哈希表枚举前缀最多查 5 次，Trie 也最多走 5 步，二者复杂度都可以接受。但如果没有词根长度上限，哈希表可能为每个单词构造很多前缀字符串。

word = "internationalization"
枚举前缀：
i, in, int, inte, inter, ...

Trie：
沿字符走；如果 root 没有 i 分支，第一步就停。

Trie 的优势在于走不通即停止，不需要构造所有候选前缀。对于大量共享前缀的词根，Trie 还会共享节点，结构表达更紧凑。

四、实现细节：数组孩子还是 Map 孩子

如果题目只包含小写英文字母，TrieNode[26] 简洁且访问快。若词根可能包含大小写、连字符、Unicode 或其他字符，使用 Map<Character, TrieNode> 更稳。面试时要根据字符集说明选择。

字符集	children 结构	优点	代价
小写 a-z	长度 26 数组	快、代码短	空指针多
大字符集	HashMap	节省稀疏空间	常数更大
静态大词典	压缩 Trie	节点少	实现复杂

不要在节点里只存 isEnd，还要能继续向下走孩子。因为一个词根可能同时是另一个词根的前缀，例如 cat 和 cattle。

五、边界：无词根、短词、标点

如果某个单词中途走不通，应返回原词。如果单词本身就是词根，也会在末尾遇到 isEnd，返回它自己。若句子包含标点，如 "battery,"，题目通常简化为小写单词和空格；真实工程要先做分词和标点处理。

dict = [bat]
word = battery  -> bat
word = bath     -> bat
word = bad      -> bad   (ba 后没有 d，且 ba 不是词根)
word = bat      -> bat

在工程里，大小写归一化也要明确：Battery 是否匹配 bat，取决于是否先转小写。算法题一般不考这个，但面试追问工程化时可以主动补充。

常见误区与追问

记忆钩子：词根替换找的是“最早结束的前缀”，不是最长前缀。

这一节的关键是把“前缀匹配”和“替换策略”分开说。Trie 负责快速找到候选前缀，但题目规则决定遇到第 1 个 isEnd 就停止；如果规则改成最长词根，才需要继续向下走并记录最后一次命中。

误区：应该找最长匹配词根。 Replace Words 要最短词根，第一次遇到 isEnd 就返回。
误区：走完整个单词后再判断。 这样会错过短词根提前替换的要求。
误区：Trie 只能判断完整单词。 Trie 更擅长前缀判断，词根替换正是前缀应用。
追问：哈希表能不能做？ 能，枚举前缀查哈希表即可；Trie 更自然且能走不通提前停。
追问：如果包含标点怎么办？ 需要先分词或清洗标点，算法核心不变。
追问：为什么 cat 和 cattle 同时存在时返回 cat？ 因为从左到右第一次命中 isEnd 的前缀最短。

加强记忆

词根替换可以记成“沿 Trie 找第一个终点”。先把所有词根插入 Trie，再对句子中的每个单词逐字符向下走；孩子不存在则原词保留，遇到 isEnd 则立刻返回当前前缀。这个题的分水岭是“最短词根”，所以不能走完整个单词才判断，也不能找最长匹配。掌握它后，路由前缀、命令别名、文本规范化这类“最短前缀替换”问题都能套同一模型。

简化版

详细版