我的笔记

🍕 前缀树

前缀树作用:

查询某字符串数量
查询以某字符为前缀的字符串数量

操作:

往前缀树中插入一个字符串
查找一个字符串的数量 (end)
查找某前缀的字符串的数量 (pass)
删除某个字符串
- 方法1: 先查找, 看看这个字符存不存在, 然后再删除
- (我认为的)方法2: 同样先查找, 但是查找过程中保存走过的路径, 如果找到, 那就就直接在路径上删除。
- 方法2: 其实和方法1 是一样的, 在时间复杂度上是一样的, 常数时间上方法2快一点点, 但是占用了更多的内存。

java

class TrieNode {
    int pass; // 构造前缀树时经过了这个节点多少次
    int end;  // 这个节点是多少个字符串的最后一个字符
    TrieNode[] nexts; // 这个节点的后面有多少个节点。 如果字符串是纯小写字母的话, nexts 数组长度为 26 初始值为 Null, 表示不存在这条路
    // 刷题过程中的, 字符的种类基本是固定的, 所以这里使用固定长度的数组形式
    // 实际项目中, 字符的种类可能是未知的, 这个时候可以使用 哈希表 的, key 就是字符, value 就是对应的 TrieNode 节点
}

class Trie {
    TrieNode root;

    Trie() {
        // 根节点上的 pass 表示的含义是以 空串 为前缀的数量, 也就是加入的字符串数量
        //          end  的含义就是 空字符串 的数量
        root = new TrieNode();
    }

    // 插入一个字符串
    void insert(String word) {
        if (word == null) {
            return;
        }
        char[] chs = word.toCharArray(); // 将字符串拆分成单个字符
        TrieNode node = root;
        node.pass++;
        int index = 0;
        for (int i = 0; i < chs.length; i++) { // 遍历单个字符, 依次建路
            index = chs[i] - 'a';
            if (node.nexts[index] == null) {
                node.nexts[index] = new TrieNode()
            }
            node = node.nexts[index];
            node.pass++;
        }
        node.end++;
    }

    // 查找某个字符的数量
    int search(String 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;
    }

    // 查询以某个字符为前缀的数量。 和 search 的区别只在于, 查询前缀返回的是 pass
    int prefixNumber(String 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.pass;
    }

    void delete(String word) [
        if (search(word) != 0) {
            char[] chs = word.toCharArray();
            TrieNode node = root;
            node.pass--;
            int index = 0;
            for (int i = 0; i < chs.length; i++) {
                index = chs[i] - 'a'
                if (--node.nexts[index].pass == 0){
                    // 如果是 c++, 需要继续访问后续的节点, 将他们的空间释放。 具体做法可以是: 不在这里释放空间, 而是先记录下来, 同时把后续要释放空间的节点记录下来
                    // 等到循环结束后, 再将节点设置为空, 同时遍历要释放空间的节点, 依次释放空间。
                    node.nexts[index] = null;
                    return;
                }
                node = node.nexts[index];
            }
            node.end--;
        }
    ]

}

🍕 前缀树 ​

🍕 前缀树