Trie树的插入，查前缀，查单词，删前缀和删单词。
2024-09-06 19:13:59
这个Trie原先用C++就敲得很熟了，看了蓝桥杯的视频后学会把一个功能这样封装起来，以后用的时候就很爽可以直接调用了，所以就用Java写了；
public class Trie {
private final int SIZE = 26;
private final int HEAD = 'a';
private int cnt;
private int tail;
private Trie[] next = new Trie[SIZE];
void insert(String s) {
Trie now = this;
for (int i = 0; i < s.length(); i++) {
int id = s.charAt(i) - HEAD;
if (now.next[id] == null) {
now.next[id] = new Trie();
}
now = now.next[id];
now.cnt++;
}
now.tail++;
}
int queryPrefix(String s) {
Trie now = this;
for (int i = 0; i < s.length(); i++) {
int id = s.charAt(i) - HEAD;
if (now.next[id] == null) {
return 0;
}
now = now.next[id];
}
return now.cnt;
}
int queryWord(String s) {
Trie now = this;
for (int i = 0; i < s.length(); i++) {
int id = s.charAt(i) - HEAD;
if (now.next[id] == null) {
return 0;
}
now = now.next[id];
}
return now.tail;
}
void deletePrefix(String s) {
int sum = queryPrefix(s);
if (sum == 0) {
return;
}
Trie now = this;
for (int i = 0; i < s.length(); i++) {
int id = s.charAt(i) - HEAD;
now.next[id].cnt -= sum;
if (now.next[id].cnt == 0) {
now.next[id] = null;
return;
}
}
}
void deleteWord(String s) {
int sum = queryWord(s);
if (sum == 0) {
return;
}
Trie now = this;
for (int i = 0; i < s.length(); i++) {
int id = s.charAt(i) - HEAD;
now.next[id].cnt -= sum;
if (now.next[id].cnt == 0) {
now.next[id] = null;
return;
}
}
now.tail -= sum;
}
}
最新文章
- H5 本地存储一
- asp.net 微信开发失效汇总
- 安装ss
- C语言初学 简单定义圆的面积计算问题
- 分享一个option样式传递给select当前选中样式
- ARM流水线(pipeline)
- JDBC技术
- Linux命令—文件目录
- odoo学习
- 408 JavaScript 变量、数据类型、正则
- AOP面向切面编程JAVA动态代理实现用户权限管理（实现篇）
- 【腾讯Bugly干货分享】职场中脱颖而出的成长秘诀
- Dynamics 365-部分用户访问环境缓慢
- bzoj4025 二分图 [分治，并查集]
- springMVC3学习--ModelAndView对象（转）
- uvm设计分析——report
- Servlet开发
- JDK1.5新特性，基础类库篇，System类
- 20145226夏艺华 《Java程序设计》 课堂实践
- Django中多种重定向方法使用