求解思路
使用二维数组tree来存储树的边关系,其中tree[i][j]表示节点i通过字符j能到达的子节点编号。
同时维护2个辅助数组:
end数组记录以某节点结尾的完整单词数量,
pass数组记录经过某节点的字符串总数。
插入操作时沿着字符路径向下走,不存在的节点就创建新节点,同时更新pass和end计数。
查询操作只需沿路径查找,返回对应的end值即可判断单词是否存在。
前缀统计则返回最后一个字符对应节点的pass值。
删除操作需要先确认单词存在,然后沿路径将pass值减1,如果某个节点的pass减到0说明没有字符串再经过它,可以直接删除后续路径提前返回,最后将end值减1。
完整代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
|
public static int MAXN = 150001;
// tree[i][j]: 节点i通过字符j('a'+j)能到达的子节点编号
public static int[][] tree = new int[MAXN][26];
// end[i]: 以节点i结尾的完整单词数量
public static int[] end = new int[MAXN];
// pass[i]: 有多少个字符串经过节点i(包括以i结尾的)
public static int[] pass = new int[MAXN];
// cnt: 当前已使用的节点编号,从1开始(0表示空)
public static int cnt;
// 初始化Trie树,cnt=1表示根节点编号为1
public static void build() {
cnt = 1;
}
// 插入一个字符串
public static void insert(String word) {
int cur = 1; // 从根节点开始
pass[cur]++; // 根节点的pass值加1
for (int i = 0, path; i < word.length(); i++) {
path = word.charAt(i) - 'a'; // 计算字符对应的路径索引(0-25)
if (tree[cur][path] == 0) {
// 如果该路径不存在,创建新节点
tree[cur][path] = ++cnt;
}
cur = tree[cur][path]; // 移动到子节点
pass[cur]++; // 子节点的pass值加1
}
end[cur]++; // 标记该节点是一个单词的结尾
}
// 查询字符串是否存在,返回该字符串的出现次数
public static int search(String word) {
int cur = 1; // 从根节点开始
for (int i = 0, path; i < word.length(); i++) {
path = word.charAt(i) - 'a';
if (tree[cur][path] == 0) {
// 路径不存在,说明该字符串不在树中
return 0;
}
cur = tree[cur][path]; // 移动到子节点
}
return end[cur]; // 返回以该节点结尾的单词数量
}
// 统计有多少个字符串以pre作为前缀
public static int prefixNumber(String pre) {
int cur = 1; // 从根节点开始
for (int i = 0, path; i < pre.length(); i++) {
path = pre.charAt(i) - 'a';
if (tree[cur][path] == 0) {
// 前缀不存在
return 0;
}
cur = tree[cur][path]; // 移动到子节点
}
return pass[cur]; // 返回经过该节点的字符串总数
}
// 删除一个字符串
public static void delete(String word) {
if (search(word) > 0) { // 只有当字符串存在时才删除
int cur = 1;
pass[cur]--; // 根节点的pass值减1
for (int i = 0, path; i < word.length(); i++) {
path = word.charAt(i) - 'a';
// 先将子节点的pass值减1,再判断是否为0
if (--pass[tree[cur][path]] == 0) {
// 如果子节点的pass变为0,说明没有其他字符串经过
// 可以直接删除这条路径,后续节点也不需要处理了
tree[cur][path] = 0;
return;
}
cur = tree[cur][path]; // 移动到子节点
}
end[cur]--; // 该节点作为结尾的单词数减1
}
}
// 清空Trie树,为下一组测试数据做准备
public static void clear() {
for (int i = 1; i <= cnt; i++) {
Arrays.fill(tree[i], 0); // 清空所有边
end[i] = 0; // 清空结尾标记
pass[i] = 0; // 清空经过计数
}
}
public static int m, op;
public static String[] splits;
public static void main(String[] args) throws IOException {
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
String line = null;
// 处理多组测试数据
while ((line = in.readLine()) != null) {
build(); // 初始化Trie树
m = Integer.valueOf(line); // 读取操作数量
for (int i = 1; i <= m; i++) {
splits = in.readLine().split(" ");
op = Integer.valueOf(splits[0]); // 操作类型
if (op == 1) {
// 操作1: 插入字符串
insert(splits[1]);
} else if (op == 2) {
// 操作2: 删除字符串
delete(splits[1]);
} else if (op == 3) {
// 操作3: 查询字符串是否存在
out.println(search(splits[1]) > 0 ? "YES" : "NO");
} else if (op == 4) {
// 操作4: 统计前缀数量
out.println(prefixNumber(splits[1]));
}
}
clear(); // 清空数据结构,为下一组数据做准备
}
out.flush();
in.close();
out.close();
}
|
如果觉得有帮助，欢迎点赞、关注、转发~