如何用 Trie 求每个单词的最短唯一前缀？

简化版

在 Trie 节点上维护 pass 计数，表示有多少个单词经过该节点。插入所有单词后，对每个单词从头走 Trie，第一次遇到 pass == 1 的位置，就是它的最短唯一前缀。

详细版

最短唯一前缀要求：对每个单词找一个最短前缀，使得词典中只有这个单词拥有该前缀。

做法：

建 Trie，插入每个单词。
每经过一个节点，就把该节点的 pass 加 1。
查询某个单词时，沿字符走 Trie。
第一次遇到 pass == 1 的节点，当前前缀就是最短唯一前缀。
如果一直没有遇到，通常完整单词就是唯一前缀，或说明有重复单词需要额外处理。

String uniquePrefix(String word) {
    Trie node = root;
    StringBuilder sb = new StringBuilder();
    for (char ch : word.toCharArray()) {
        node = node.children[ch - 'a'];
        sb.append(ch);
        if (node.pass == 1) return sb.toString();
    }
    return sb.toString();
}

总复杂度是所有单词字符数级别，空间也是 Trie 节点数。

完整版教学

一、什么叫“唯一前缀”

一个前缀是唯一的，意思是词典里只有一个单词以它开头。比如 ["zebra", "dog", "duck", "dove"] 中，z 只属于 zebra，所以 zebra 的最短唯一前缀是 z；dog 和 dove 都以 do 开头，所以 dog 至少要到 dog 才唯一。

zebra -> z
dog   -> dog
duck  -> du
dove  -> dov

这个问题本质是在问“某个前缀下面有多少个单词”。Trie 节点正好对应前缀，所以在节点上挂计数非常自然。

二、pass 计数的含义

pass 表示有多少个单词经过这个节点，也就是有多少个单词拥有该节点对应的前缀。插入单词时，每走到一个字符节点，就给 pass 加 1。这样查询时只要看 pass，就知道当前前缀是否唯一。

words = [dog, duck, dove]

root
└─ d(pass=3)
   ├─ o(pass=2)
   │  ├─ g(pass=1)
   │  └─ v(pass=1) -> e
   └─ u(pass=1) -> c -> k

对 duck 来说，走到 d 时 pass=3，不唯一；走到 du 时 pass=1，所以最短唯一前缀是 du。

三、为什么第一次 pass==1 就是最短

查询单词时从第 1 个字符开始向后走，前缀长度逐步增加。第一次遇到 pass==1，说明当前前缀已经只有这个单词拥有；由于更短的前缀都已经检查过且 pass>1，所以当前前缀必然是最短唯一前缀。

word = dove
d    pass=3  不唯一
do   pass=2  不唯一
dov  pass=1  唯一，立即返回
dove 不需要继续

这和词根替换里的“第一次命中即可返回”很像，只是判断条件从 isEnd 换成了 pass==1。理解这个相似性，可以把很多 Trie 变体联系起来。

四、和排序相邻比较的方案对比

最短唯一前缀也可以用排序：把单词按字典序排序后，一个单词只需要和相邻单词比较最长公共前缀，再取较大值加一。但排序方案需要额外处理原顺序映射，逻辑不如 Trie 直观。

方案	核心信息	时间复杂度	特点
Trie + pass	每个前缀覆盖多少单词	`O(S)`	适合动态插入
排序相邻比较	相邻词最长公共前缀	`O(N log N + S)`	不建树
暴力比较	与所有其他词比前缀	`O(N^2 * L)`	简单但慢

Trie 的优势是前缀计数清晰，而且如果后续还要支持新增单词，只需更新路径 pass。

五、重复单词和删除的边界

如果词典中允许重复单词，那么完整单词路径的 pass 可能仍大于 1，此时不存在能区分两个相同单词的字符前缀。题目一般默认单词唯一；如果不唯一，要定义返回完整词还是附加编号。

删除单词时也要沿路径把 pass 减 1，并在节点无人经过时清理。否则最短唯一前缀会被已删除的单词影响。pass 是动态计数，必须和插入删除保持一致。

插入 dog, dove:
do.pass = 2
删除 dove 后:
do.pass = 1
dog 的最短唯一前缀可以从 dog 缩短为 d 或 do，取决于其他 d 前缀单词。

工程实现里还要小心大小写和字符集，字符集大时用 Map 孩子更合适。

常见误区与追问

记忆钩子：最短唯一前缀找的是第一处 pass 从多人共享变成只剩自己的节点。

误区：用 isEnd 就能判断唯一前缀。 isEnd 只说明是否是完整单词，不说明有多少单词共享该前缀。
误区：最后一个字符才可能唯一。 很多单词在很短前缀处就已经 pass==1。
误区：节点存在就代表唯一。 节点存在只代表至少一个单词经过，要看 pass 是否等于 1。
追问：重复单词怎么办？ 纯字符前缀无法区分完全相同的单词，需要题目额外定义。
追问：排序也能做吗？ 能，比较相邻单词的最长公共前缀，但 Trie 的前缀计数更直接。
追问：删除后如何维护？ 沿删除单词路径把 pass 减 1，必要时清理无人经过的节点。

加强记忆

最短唯一前缀的关键字段是 pass。每个 Trie 节点代表一个前缀，pass 表示有多少单词共享这个前缀；查询某个单词时，从短到长走路径，第一次遇到 pass==1 就返回。记忆时把它和 isEnd 分开：isEnd 回答“这里是不是一个完整词”，pass 回答“这个前缀属于几个人”。唯一前缀看的是人数，所以必须靠计数。

简化版

详细版