前缀树

Trie树 = 前缀树 = 字典树

https://leetcode-cn.com/problems/implement-trie-prefix-tree/

使用场景：给两个数组，A = {"abc","bce","abd","bef"}, B = {"be","abc"}问：

1.B中哪些字符串是在A中出现的

2.A中哪些字符串是，以B中某个字符串为前缀的

3.问以"e"结尾的字符串有哪些？

思路：对A中所有字符串建立前缀树： "O"代表节点，"/"和"\"代表边，字符存在边上，

O                  每个节点还存着边上字符添加的次数以及以该节点边上字符结束的次数

a /       \ b            所以节点的数据结构如下，nodes表示当前节点指向的下一节点

O         O             Node {int path;int end; Node[] nodes}

b /           /c   \ e

O          O    O

c /  d\       /e    /f

O     O   O     O

	public class Code_01_TrieTree {



	





	 public static class TrieNode { 



	 public int path; 



	 public int end; 



	public TrieNode[] nexts;



	





	public TrieNode() {



	path = 0;



	end = 0;



	nexts = new TrieNode[26]; // 字母有26位 



	}



	}



	





	 public static class Trie { 



	private TrieNode root;



	





	public Trie() {



	root = new TrieNode();



	}



	





	public void insert(String word) {



	if (word == null) {



	 return; 



	}



	char[] chs = word.toCharArray();



	TrieNode node = root;



	int index = 0;



	for (int i = 0; i < chs.length; i++) { // 遍历每一个字符 



	 index = chs[i] - 'a'; // 字符与'a'的距离表示下一节点的边上存着的字符



	if (node.nexts[index] == null) {



	node.nexts[index] = new TrieNode();



	}



	 node = node.nexts[index]; // 节点一直向下走 



	node.path++;



	}



	 node.end++; // 节点停留在最后一个字符，以该节点结尾的次数+1



	}



	





	public void delete(String word) {



	if (search(word) != 0) {



	char[] chs = word.toCharArray();



	TrieNode node = root;



	int index = 0;



	for (int i = 0; i < chs.length; i++) {



	index = chs[i] - 'a';



	 if (--node.nexts[index].path == 0) { // 找到匹配的字符，如果该字符只出现过一次，该字符所在的节点的上一节点直接指向null，无需匹配后面的



	node.nexts[index] = null;



	return;



	}



	 node = node.nexts[index]; 



	}



	node.end--;



	}



	}



	





	 public int search(String word) { // 有没有相同的字符串，字符串word在前缀树中出现了几次，



	if (word == null) {



	return 0;



	}



	char[] chs = word.toCharArray();



	TrieNode 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; // 跟插入差不多，找到最后一个字符的节点，返回节点上以该字符串结尾的次数



	}



	





	public int prefixNumber(String pre) { // 以pre为前缀 



	if (pre == null) {



	return 0;



	}



	char[] chs = pre.toCharArray();



	TrieNode 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.path;



	}



	}



	



	public static void main(String[] args) {  



	





	Trie trie = new Trie();



	System.out.println(trie.search("jin"));



	trie.insert("jin");



	System.out.println(trie.search("jin"));



	trie.delete("jin");



	System.out.println(trie.search("jin"));



	trie.insert("jina");



	trie.insert("jinb");



	System.out.println(trie.prefixNums("jin"));



	}



	}