一、前缀树
1.1前缀树相关知识
1.前缀树的概念：前缀树又叫字典树或单词查找树（高效的存储和查找字符串集合的数据结构）。
2.主要应用场景：给定一个字符串集合构建一颗前缀树，然后给定一个字符串，判断前缀树中是否包含该字符串或者该字符串的前缀。
3.存储形式：存储的字符串可能：全是 小写字母 或全是 大写字母 或全是 数字 或全是 0和1
4.字典树的核心思想是：利用字符串之间的公共前缀来节省存储空间和提高查询效率。它是一棵多叉树，每个节点代表一个字符串的前缀，从根节点到叶子节点的路径组成一个字符串。字典树的根节点不包含字符，每个子节点代表一个字符，从根节点到任意一个节点所经过的路径上的字符连接起来即为该节点所代表的字符串。每个节点可以存储一个或多个字符串，通常使用一个标志来标记一个节点代表的字符串是否存在。当需要在一组字符串中查找某个字符串时，可以利用字典树来实现高效的查找操作。
1.2前缀树的举例
- 根结点不保存字符
- 前缀树是一颗多叉树
- 前缀树的每个节点保存一个字符
- 具有相同前缀的字符串保存在同一条路径上
- 字符串的尾处相应的在前缀树上也有结束的标志
编辑
二、前缀树的实现
2.1数组实现前缀树
2.1.1插入字符串
private static final int[][] son=new int[100000][26];//26个字母，一共100000个数据 private static final int[] count=new int[100000];//存储以当前这个点结尾的单词有多少个 private int index=0;//下标为0的点，既是根节点，又是空节点 public void insert(char[] str){ int parent=0; for(int i=0;i<str.length;i++){ int cur=str[i]-'a'; if(son[parent][cur]==0){ son[parent][cur]=++index; } parent=son[parent][cur]; } count[parent]++; }
2.1.2查找字符串
private static final int[][] son=new int[100000][26];//26个字母，一共100000个数据 private static final int[] count=new int[100000];//存储以当前这个点结尾的单词有多少个 private int index=0;//下标为0的点，既是根节点，又是空节点 public int query(char[] str){ int parent=0; for(int i=0;i<str.length;i++){ int cur=str[i]-'a'; if(son[parent][cur]==0){ return 0; } parent=son[parent][cur]; } return count[parent]; }
2.1.3代码实现
import java.util.Scanner; class Trie { private int[][] son=new int[100010][26];//26个字母，一共100000个数据 private int[] count=new int[100010];//存储以当前这个点结尾的单词有多少个 private int index=0; public Trie() { } public void insert(String word) { char[] str=word.toCharArray(); //parent表示行 int parent=0; for(int i=0;i<str.length;i++){ //cur表示列,列表示字符串的开头元素 int cur=str[i]-'a'; if(son[parent][cur]==0){ son[parent][cur]=++index; } parent=son[parent][cur]; } count[parent]++; } public boolean search(String word) { char[] str=word.toCharArray(); int parent=0; for(int i=0;i<str.length;i++){ int cur=str[i]-'a'; if(son[parent][cur]==0){ return false; } parent=son[parent][cur]; } return count[parent]!=0; } public boolean startsWith(String prefix) { char[] str=prefix.toCharArray(); int parent=0; for(int i=0;i<str.length;i++){ int cur=str[i]-'a'; if(son[parent][cur]==0){ return false; } parent=son[parent][cur]; } return true; } }
2.2哈希表实现前缀树
2.2.1插入字符串
public void insert(String word) { Trie trie = this;//获得根结点 for (char c : word.toCharArray()) { if (trie.next.get(c) == null) {//当前结点不存在 trie.next.put(c, new Trie());//创建当前结点 } trie = trie.next.get(c);//得到字符c的结点,继续向下遍历 } trie.isEnd = true; }
2.2.2查找字符串
public boolean search(String word) { Trie trie = this;//获得根结点 for (char c : word.toCharArray()) { if (trie.next.get(c) == null) {//当前结点不存在 return false; } trie = trie.next.get(c);//得到字符c的结点,继续向下遍历 } return trie.isEnd; }
2.2.3查找前缀
public boolean startsWith(String prefix) { Trie trie = this;//获得根结点 for (char c : prefix.toCharArray()) { if (trie.next.get(c) == null) {//当前结点不存在 return false; } trie = trie.next.get(c);//得到字符c的结点,继续向下遍历 } return true; }
2.2.4代码实现
public class Trie { Map<Character, Trie> next; boolean isEnd; public Trie() { this.next = new HashMap<>(); this.isEnd = false; } public void insert(String word) { Trie trie = this;//获得根结点 for (char c : word.toCharArray()) { if (trie.next.get(c) == null) {//当前结点不存在 trie.next.put(c, new Trie());//创建当前结点 } trie = trie.next.get(c);//得到字符c的结点,继续向下遍历 } trie.isEnd = true; } public boolean search(String word) { Trie trie = this;//获得根结点 for (char c : word.toCharArray()) { if (trie.next.get(c) == null) {//当前结点不存在 return false; } trie = trie.next.get(c);//得到字符c的结点,继续向下遍历 } return trie.isEnd; } public boolean startsWith(String prefix) { Trie trie = this;//获得根结点 for (char c : prefix.toCharArray()) { if (trie.next.get(c) == null) {//当前结点不存在 return false; } trie = trie.next.get(c);//得到字符c的结点,继续向下遍历 } return true; } }
