前缀树学习
1.长什么样子
2.重要的组成部分
class Trie {private Trie[] children;private boolean isEnd;public Trie() {children = new Trie[26];isEnd = false;}
}
假如我们只构建一个只有26个英文小写字母的前缀树
那么children的长度就是26 ,如果children[i] 不为空,那么证明有某个单词使用了这个前缀
3.插入方法
public void insert(String word) {Trie node = this;for(int i = 0;i<word.length();i++){char ch = word.charAt(i);int index = ch-'a';if(node.children[index]==null){node.children[index] = new Trie();}node = node.children[index];}node.isEnd = true;}
1.从root节点开始->计算单词索引->插入到children的正确位置上->改变指针
遍历完成后,记得加上一个标识证明这里是一个结尾
4.搜索方法
private Trie searchPrefix(String prefix){Trie node = this;for(int i = 0;i<prefix.length();i++){char ch = prefix.charAt(i);int index = ch-'a';if(node.children[index]==null){return null;}node = node.children[index];}return node;}
搜索前缀的方法,差不多是插入方法的逆向思路
如果我们要找到某个单词,只用判断isEnd,或者判断是否存在某个前缀,只有判断是否为null
public boolean search(String word) {Trie node = searchPrefix(word);return node!=null && node.isEnd;}public boolean startsWith(String prefix) {return searchPrefix(prefix)!=null;}
5.leetcode题目练习
208. 实现 Trie (前缀树) | 力扣 | LeetCode | 🟠
上文的前缀树的实现就是这题
648. 单词替换 | 力扣 | LeetCode | 🟠
可以先把字典构建一个前缀树
我们需要对搜索方法进行一个小小的修改
对于每个单词,需要进行替换,那么可以先创建一个StringBuilder
对该单词的每个字符,进行前缀树匹配,匹配上了,sb就append,然后移动前缀树指针,如果有某个字符匹配不上,直接返回单词原型
如果前缀树已经到了末尾,返回sb即可
211. 添加与搜索单词 - 数据结构设计 | 力扣 | LeetCode | 🟠
其实这里需要注意的就是通配符的处理
对于没有通配符,和上面正常搜索就行
有通配符,需要遍历每一个children 相当于就是dfs
677. 键值映射 | 力扣 | LeetCode | 🟠
这题,需要加一个字段也就是int val;代表值
首先根据searchPrefix方法找到前缀
然后计算和,计算代码如下
public int prefixSum(Trie prefix){int sum = prefix.isEnd ? prefix.val : 0;for(int i = 0;i<26;i++){Trie child = prefix.children[i];if(child!=null){sum +=prefixSum(child);}}return sum;}
if(child!=null){sum +=prefixSum(child);}}return sum;
}
