# 前缀树（prefix tree/trie）
# 可以完成前缀相关的查询
# 核心思路
- 单个字符串中，字符从前到后的加到一棵多叉树上
- 字符放在路上，节点上有专属的数据项（常见的是pass和end值）(顶点就是空的)
- 所有样本都这样添加，如果没有路就新建，如有路就复用
- 沿途节点的pass值增加1，每个字符串结束时来到的节点end值增加1
# 核心方法
设计一种结构。用户可以：
1）void insert(String str) //添加某个字符串，可以重复添加，每次算1个
2）int search(String str) //查询某个字符串在结构中还有几个
3) void delete(String str) //删掉某个字符串，可以重复删除，每次算1个
4）int prefixNumber(String str) //查询有多少个字符串，是以str做前缀的
# 两种实现方式之-代码示例-数组实现
路数固定的,适合用数组的方式实现,例如小写单词,因为用数组替代,常数时间更好,速度更快.
package class08;
public class Code01_Trie {
// 测试链接 : https://leetcode.cn/problems/implement-trie-ii-prefix-tree/
// 提交Trie类可以直接通过
// 原来代码是对的，但是既然找到了直接测试的链接，那就直接测吧
// 这个链接上要求实现的功能和课上讲的完全一样
// 该前缀树的路用数组实现
class Trie {
class Node {
public int pass;
public int end;
//因为是小写字母,所以只有26条路,减去小写a的ascii码即可得到数字值.
public Node[] nexts;
public Node() {
pass = 0;
end = 0;
nexts = new Node[26];
}
}
private Node root;
public Trie() {
root = new Node();
}
/**
有途径的节点,pass++,代表经过的词的路径增加了.
如果新的字母,没有已有的,新建路,路++,如果否则不新建
如果没有单词了,当前点的end++
*/
public void insert(String word) {
if (word == null) {
return;
}
char[] str = word.toCharArray();
Node node = root;
node.pass++;
int path = 0;
for (int i = 0; i < str.length; i++) { // 从左往右遍历字符
path = str[i] - 'a'; // 由字符，对应成走向哪条路
if (node.nexts[path] == null) {
node.nexts[path] = new Node();
}
node = node.nexts[path];
node.pass++;
}
node.end++;
}
/**
pass 减完了等于 0的点,删除掉,
否则只是减路径
*/
public void erase(String word) {
if (countWordsEqualTo(word) != 0) {
char[] chs = word.toCharArray();
Node node = root;
node.pass--;
int path = 0;
for (int i = 0; i < chs.length; i++) {
path = chs[i] - 'a';
if (--node.nexts[path].pass == 0) {
node.nexts[path] = null;
return;
}
node = node.nexts[path];
}
node.end--;
}
}
/**
判断一个单词出现了几次,找到节点的end的值,就是以他为点的
*/
public int countWordsEqualTo(String word) {
if (word == null) {
return 0;
}
char[] chs = word.toCharArray();
Node node = root;
int index = 0;
for (int i = 0; i < chs.length; i++) {
index = chs[i] - 'a';
if (node.nexts[index] == null) {
return 0;
}
node = node.nexts[index];
}
return node.end;
}
/**
求一个单词前缀的出现了几次,找到途经点的path,即可知道.
*/
public int countWordsStartingWith(String pre) {
if (pre == null) {
return 0;
}
char[] chs = pre.toCharArray();
Node node = root;
int index = 0;
for (int i = 0; i < chs.length; i++) {
index = chs[i] - 'a';
if (node.nexts[index] == null) {
return 0;
}
node = node.nexts[index];
}
return node.pass;
}
}
}
# 两种实现方式之-代码示例-哈希表实现
路数不固定的,适合用map这种方式实现.
package class08;
import java.util.HashMap;
public class Code02_Trie {
// 测试链接 : https://leetcode.cn/problems/implement-trie-ii-prefix-tree/
// 提交Trie类可以直接通过
// 原来代码是对的，但是既然找到了直接测试的链接，那就直接测吧
// 这个链接上要求实现的功能和课上讲的完全一样
// 该前缀树的路用哈希表实现
class Trie {
class Node {
public int pass;
public int end;
public HashMap<Integer, Node> nexts;
public Node() {
pass = 0;
end = 0;
nexts = new HashMap<>();
}
}
private Node root;
public Trie() {
root = new Node();
}
public void insert(String word) {
if (word == null) {
return;
}
char[] chs = word.toCharArray();
Node node = root;
node.pass++;
int index = 0;
for (int i = 0; i < chs.length; i++) {
index = (int) chs[i];
if (!node.nexts.containsKey(index)) {
node.nexts.put(index, new Node());
}
node = node.nexts.get(index);
node.pass++;
}
node.end++;
}
public void erase(String word) {
if (countWordsEqualTo(word) != 0) {
char[] chs = word.toCharArray();
Node node = root;
node.pass--;
int index = 0;
for (int i = 0; i < chs.length; i++) {
index = (int) chs[i];
if (--node.nexts.get(index).pass == 0) {
node.nexts.remove(index);
return;
}
node = node.nexts.get(index);
}
node.end--;
}
}
public int countWordsEqualTo(String word) {
if (word == null) {
return 0;
}
char[] chs = word.toCharArray();
Node node = root;
int index = 0;
for (int i = 0; i < chs.length; i++) {
index = (int) chs[i];
if (!node.nexts.containsKey(index)) {
return 0;
}
node = node.nexts.get(index);
}
return node.end;
}
public int countWordsStartingWith(String pre) {
if (pre == null) {
return 0;
}
char[] chs = pre.toCharArray();
Node node = root;
int index = 0;
for (int i = 0; i < chs.length; i++) {
index = (int) chs[i];
if (!node.nexts.containsKey(index)) {
return 0;
}
node = node.nexts.get(index);
}
return node.pass;
}
}
}