LeetCode 补充题 152. 支持删除和词频统计的字典树
题目描述
:::fold-green 相关原题
LeetCode 原题： ✅ 1804. 实现 Trie （前缀树） II
本文沿用支持重复词、删除和前缀计数的 Trie 模型；完整词查询使用布尔返回值，操作名称与力扣接口不同。
:::
实现一个只含小写英文字母的 Trie，支持以下操作：
insert：加入一个单词，允许重复。delete：删除单词的一次出现。search：判断完整单词是否存在。prefixNumber：返回以给定前缀开头的单词数量，重复词重复计数。删除后不能影响其他共享前缀的单词。本题保证删除的单词存在，本文接口对不存在的词直接忽略。
示例 1：
输入：
操作 = [insert("apple"), insert("apple"), insert("app"), prefixNumber("app"), delete("apple"), prefixNumber("app"), search("apple"), delete("apple"), search("apple"), search("app")]
输出：查询结果 = [3,2,true,false,true]
解释： 第一次删除只移除一个apple；第二次删除后apple不再存在，app仍保留。insert和delete不产生查询结果。
提示：
- 操作数满足
0<= m <= 10^5 - 字符串长度都满足
0 <= n <= 20
题意分析
单词可以重复，终点布尔标记不足以表示剩余份数；前缀查询还需要统计经过某节点的全部词。因此每个节点分别保存路径计数和完整词计数，删除时按一份出现次数递减。
解法：Trie 路径次数与终止次数
核心思路
[!blue]
pass是经过当前节点的单词份数，end是恰在此结束的份数。插入时根与沿途节点的pass都加 1，末尾end加 1。查找前缀返回终点pass，查找完整词则检查end > 0。删除先确认完整词存在，再沿同一路径减计数。若某个孩子的
pass变为 0，说明没有任何词再使用整条分支，可直接断开并结束；否则走到词末尾只将end减 1，其他共享前缀和重复份数仍保留。根也参与计数，使空前缀查询得到全部词数；空词插入或删除只改根的
pass、end。Go 需通过NewTrie初始化根，避免从空指针开始操作。
解题步骤
- 每个节点记录26条子边、经过次数和终止次数。
- 插入逐层增加经过次数，末尾增加终止次数。
- 删除逐层减少计数，经过次数为0时断开无用分支。
- 完整查询检查终止次数，前缀查询返回经过次数。
代码实现
class Trie {
private static class Node {
Node[] next = new Node[26];
int pass;
int end;
}
private final Node root = new Node();
private Node find(String s) {
Node node = root;
for (int i = 0; i < s.length(); i++) {
node = node.next[s.charAt(i) - 'a'];
if (node == null) {
return null;
}
}
return node;
}
public void insert(String word) {
Node node = root;
node.pass++;
for (int i = 0; i < word.length(); i++) {
int c = word.charAt(i) - 'a';
if (node.next[c] == null) {
node.next[c] = new Node();
}
node = node.next[c];
node.pass++;
}
node.end++;
}
public boolean search(String word) {
Node node = find(word);
return node != null && node.end > 0;
}
public int prefixNumber(String prefix) {
Node node = find(prefix);
return node == null ? 0 : node.pass;
}
public void delete(String word) {
if (!search(word)) {
return;
}
Node node = root;
node.pass--;
for (int i = 0; i < word.length(); i++) {
int c = word.charAt(i) - 'a';
Node child = node.next[c];
if (--child.pass == 0) {
node.next[c] = null;
return;
}
node = child;
}
node.end--;
}
}
type trieNode struct {
next [26]*trieNode
pass, end int
}
type Trie struct{ root *trieNode }
func NewTrie() *Trie {
return &Trie{root: &trieNode{}}
}
func (t *Trie) find(s string) *trieNode {
node := t.root
for i := 0; i < len(s); i++ {
node = node.next[s[i]-'a']
if node == nil {
return nil
}
}
return node
}
func (t *Trie) Insert(word string) {
node := t.root
node.pass++
for i := 0; i < len(word); i++ {
c := word[i] - 'a'
if node.next[c] == nil {
node.next[c] = &trieNode{}
}
node = node.next[c]
node.pass++
}
node.end++
}
func (t *Trie) Search(word string) bool {
node := t.find(word)
return node != nil && node.end > 0
}
func (t *Trie) PrefixNumber(prefix string) int {
node := t.find(prefix)
if node == nil {
return 0
}
return node.pass
}
func (t *Trie) Delete(word string) {
if !t.Search(word) {
return
}
node := t.root
node.pass--
for i := 0; i < len(word); i++ {
c := word[i] - 'a'
child := node.next[c]
child.pass--
if child.pass == 0 {
node.next[c] = nil
return
}
node = child
}
node.end--
}
复杂度分析
- 时间复杂度：每次操作时间 $O(L)$，L为单词/前缀长度。
- 空间复杂度：存储空间 $O(S)$，S为保留路径节点数。
关键点总结
[!green]
删除先确认单词存在，再沿同一条路径递减；某条分支pass变成0时可整段断开；前缀数量就是前缀末尾节点的pass，完整单词则检查end。
易错点总结
[!yellow]
布尔终点不能表示重复插入；删除一个词不能清掉共享前缀；前缀计数和完整词计数不同；Go使用NewTrie初始化。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 208. 实现 Trie (前缀树) | 中等 | 将布尔终止标记扩展为次数，并增加 pass 以支持重复词、前缀数量和删除。 |
| 677. 键值映射 | 中等 | 同样维护前缀聚合，本题累计词的出现次数，键值映射累计数值且覆盖时要更新差量。 |