前缀树:每次加字符都从头结点开始加,看有没有通向该字符的路有就复用,没有就新建。
e(end):到该字符为止,该字符串被加入几次。例如:问“bk”字符串被加入几次,发现k处的e=0,则说明一次都没被加入过。
p(pass):经过该字符有几次。例如:问以”ab“开头的字符串有几个,发现b的p=3,所以有3个。
头节点即代表有多少个以空“”开头的字符串,也代表你总共加入多少个字符串
数组(例如:26个字母)
hash表
插入字符串构建前缀树
在前缀树查找字符串出现几次
提前没路
查找有多少个以某字符串开头的字符串
删除
你如果想删abc,是只删一次的。即沿途p–,最后一个e–
在沿途p–的时候减成0了,怎么办?
删除时d的p减为0,将d下面的结点置为空,释放结点
先判断这个word之前加入过没有
下一个节点p减后=0,将其下结点置空
题解
代码:
import java.util.*;
public class Solution {
public class TrieTreeNode{
public int pass;
public int end;
public TrieTreeNode[] nexts;//接下来的有26条路
//构造方法
public TrieTreeNode() {
pass = 0;
end = 0;
nexts = new TrieTreeNode[26];
}
}
private TrieTreeNode root=new TrieTreeNode();//根节点
//插入方法
public void insert(String word) {
if (word == null) return;
//先将字符串转为字符数组
char[] chars = word.toCharArray();
//从根节点开始遍历,沿途pass++
TrieTreeNode node = root;
node.pass++;
int path = 0;
for (int i = 0; i < chars.length; i++) {
//获得要选择的那条路
path = chars[i] - 'a';
//如果路不存在就创建
if (node.nexts[path] == null) {
node.nexts[path] = new TrieTreeNode();
}
//路存在,就将当前节点下移,沿途pass++
node = node.nexts[path];
node.pass++;
}
//到字符串最后end++
node.end++;
}
//删除
public void delete(String word){
if (word==null) return;
//先查找一下看该字符串是否存在,存在再删除
int searchNumbers = search(word);
if(searchNumbers==0) return;
char[] chars = word.toCharArray();
//从根节点开始
TrieTreeNode node=root;
//根节点的pass--
node.pass--;
int path=0;
for (int i = 0; i <chars.length ; i++) {
path=chars[i]-'a';
if(--node.nexts[path].pass==0){
//当该节点减1后,pass变成了0(说明该节点之前插入的字符只有一次还是我们要删除的字符串,那下面就不用再查找了,直接将后面字符串置为空)
node.nexts[path]=null;
return;
}
node=node.nexts[path];//游标继续下移
}
node.end--;//最后将该字符串结尾的字符end--
}
//搜索方法,在前缀树查找字符串出现几次
public int search(String word) {
if (word == null) return 0;
char[] chars = word.toCharArray();
//从根节点开始遍历
TrieTreeNode node = root;
int path = 0;
for (int i = 0; i < chars.length; i++) {
path = chars[i] - 'a';
if (node.nexts[path] == null) {
return 0;//说明之前没有插入过
}
node = node.nexts[path];//之前插入过,结点下移
}
return node.end;//到字符串最后一个字符
}
//查找有多少个以某字符串开头的字符串(和上一个方法唯一的区别就是返回值不一样,一个是end,一个是pass)
public int prefixNumber(String word){
if(word==null) return 0;
char[] chars = word.toCharArray();
//从根节点开始
TrieTreeNode node=root;
int path=0;
for (int i = 0; i <chars.length ; i++) {
path=chars[i]-'a';
if(node.nexts[path]==null){//没路就返回0
return 0;
}
node=node.nexts[path];//有路就继续下移
}
return node.pass;
}
/**
*
* @param operators string字符串二维数组 the ops
* @return string字符串一维数组
*/
public String[] trieU (String[][] operators) {
// write code here
ArrayList<String> list=new ArrayList();
//TrieTree trie=new TrieTree();
for(int i=0;i<operators.length;i++){
if(Integer.parseInt(operators[i][0])==1){
insert(operators[i][1]);
}else if(Integer.parseInt(operators[i][0])==2){
delete(operators[i][1]);
}else if(Integer.parseInt(operators[i][0])==3){
int r=search(operators[i][1]);
list.add(r==0?"NO":"YES");
}else{
list.add(prefixNumber(operators[i][1])+"");
}
}
return list.toArray(new String[list.size()]);
}
}