前缀树

前缀树是一种可以完成前缀相关查询的树状结构。其构建过程如下：

1. 单个字符串中，字符从前到后的加到一棵多叉树上；
2. 字符放在路上，节点上有专属的数据项（常见的是 pass 和 end 值）；
3. 所有样本都这样添加，如果没有路就新建，如有路就复用；
4. 沿途节点的 pass 值增加 1，每个字符串结束时来到的节点 end 值增加 1 。

代码实现不是很复杂，主要注意删除一个字符串时，需要先判断是否存在。当最后一个字符删除后，其 pass 值为 0，要依次删除（释放）后续的子节点（路径已经没用了）。

class Node {
    public int pass;
    public int end;
    public Node[] nexts;

    public Node() {
        this.pass = 0;
        this.end = 0;
        this.nexts = new Node[26];
    }
}

public class Trie {

    private Node root;

    public Trie() {
        this.root = new Node();
    }

    public void insert(String word) {
        if (word == null || word.isBlank()) {
            return;
        }
        // 来到节点，pass++
        Node node = root;
        node.pass++;

        char[] chars = word.toCharArray();
        int path = 0;
        for (int i = 0; i < chars.length; i++) {
            path = chars[i] - 'a';
            if (node.nexts[path] == null) {
                node.nexts[path] = new Node();
            }
            node = node.nexts[path];
            node.pass++;
        }
        // 最后一个节点 end++
        node.end++;
    }

    public void delete(String word) {
        if (word == null || word.isBlank()) {
            return;
        }
        if (countMatches(word) == 0) {
            throw new UnsupportedOperationException("Word not found in Trie: " + word);
        }

        Node node = root;
        // 来到节点就 pass--
        node.pass--;

        char[] chars = word.toCharArray();
        int path = 0;
        for (int i = 0; i < chars.length; i++) {
            path = chars[i] - 'a';
            if (--node.nexts[path].pass == 0) {
                node.nexts[path] = null;
                return;
            }
            node = node.nexts[path];
        }
        // 最后一个节点 end--
        node.end--;
    }

    public int countMatches(String word) {
        if (word == null || word.isBlank()) {
            return 0;
        }
        Node node = root;
        char[] chars = word.toCharArray();
        int path = 0;
        for (int i = 0; i < chars.length; i++) {
            path = chars[i] - 'a';
            if (node.nexts[path] == null) {
                // 下一个字符不匹配
                return 0;
            }
            node = node.nexts[path];
        }
        return node.end;
    }

    // 查询有多少个字符串匹配到前缀，返回 node.pass
    public int countStartsWith(String prefix) {
        if (prefix == null || prefix.isBlank()) {
            return 0;
        }
        Node node = root;
        char[] chars = prefix.toCharArray();
        int path = 0;
        for (int i = 0; i < chars.length; i++) {
            path = chars[i] - 'a';
            if (node.nexts[path] == null) {
                return 0;
            }
            node = node.nexts[path];
        }
        return node.pass;
    }
}