前缀树学习

前缀树学习

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;
}