如何用 Trie 统计某个前缀下有多少个单词？

简化版

可以在 Trie 节点上维护一个 passCount，表示有多少个单词经过这个节点。

插入单词时，每走到一个节点就把 passCount + 1。查询某个前缀时，先沿前缀走到对应节点，如果能走到，就返回该节点的 passCount；如果中途断了，就返回 0。

如果还要统计某个完整单词出现次数，可以额外维护 endCount。

详细版

普通 Trie 只能判断某个单词或前缀是否存在。要统计前缀数量，需要给节点加计数字段。

字段	含义
passCount	有多少单词经过该节点
endCount	有多少单词以该节点结尾

例如插入 apple、app、ape 后，前缀 ap 对应节点的 passCount 是 3。

insert(word):
  cur = root
  for ch in word:
    cur = cur.children[ch]
    cur.passCount++

查询前缀数量只需要走完前缀，复杂度是 O(prefix.length)。

完整版教学

1. 普通 Trie 为什么不够

普通 Trie 通常能回答两个问题：

• 单词是否存在；
• 是否存在某个前缀。

但它不能直接回答「有多少个单词以 pre 开头」。

如果没有额外计数，你只能找到前缀节点后，再 DFS 遍历整棵子树统计结尾节点。前缀很短、子树很大时，这会很慢。

2. passCount 的含义

passCount 表示有多少个单词经过当前节点。

例如插入：

app
apple
ape

路径 a -> p 被 3 个单词经过，所以 ap 节点的 passCount = 3。

前缀统计的关键是把「子树里有多少单词」提前维护在前缀节点上。

3. endCount 的含义

endCount 表示有多少个单词在当前节点结束。

它和 passCount 不同：

字段	统计对象
passCount	经过当前前缀的单词数
endCount	正好等于当前前缀的单词数

如果允许重复插入 app 两次，那么 app 节点的 endCount 可以是 2。

4. 插入时怎么更新

插入单词时，每经过一个字符节点，就把该节点的 passCount 加 1。

insert(word):
  cur = root
  for ch in word:
    if cur.children[ch] == null:
      cur.children[ch] = new Node()
    cur = cur.children[ch]
    cur.passCount += 1
  cur.endCount += 1

是否给 root 也加 passCount 看需求。如果要统计总单词数，可以维护 root 计数。

5. 查询前缀数量怎么做

查询 countPrefix(prefix) 时，只需要沿着前缀字符走。

countPrefix(prefix):
  cur = root
  for ch in prefix:
    if cur.children[ch] == null:
      return 0
    cur = cur.children[ch]
  return cur.passCount

复杂度是 O(m)，其中 m 是前缀长度，和词典总规模无关。

6. 删除时计数如何维护

如果支持删除，就要把路径上的 passCount 减 1，最后 endCount 减 1。

删除前要先确认单词存在，否则会把计数减错。

操作	对 passCount	对 endCount
插入	路径节点加 1	结尾节点加 1
删除	路径节点减 1	结尾节点减 1
查询前缀	返回前缀节点 passCount	不用遍历

当某个节点 passCount 变成 0 时，可以释放它的子树。

7. 重复单词要特别说明

如果题目不允许重复插入，endCount 可以用 boolean。

如果允许重复插入，必须用计数。

例如插入两次 app：

endCount(app) = 2
passCount(a) 至少加 2

这会影响删除和前缀统计，面试时要主动问清楚或说明假设。

8. 常见误区与追问

• 误区：前缀统计只需要 isEnd 字段。 isEnd 只能判断单词结束，不能快速统计子树单词数。
• 误区：查询前缀数量要 DFS 子树。 可以，但会慢；维护 passCount 后只走前缀路径即可。
• 误区：删除时只改 endCount。 路径上的 passCount 也要同步减少。
• 追问：重复单词怎么处理？ 用 endCount 表示完整单词出现次数，而不是 boolean。
• 追问：root 的 passCount 要不要维护？ 如果需要总词数或空前缀统计，可以维护；否则不是必须。