Trie 前缀树基础

什么是 Trie？

Trie（前缀树/字典树）是一种多叉树结构，每个节点存储一个字符，从根到叶的路径表示一个字符串。

设计价值：

• 查找/插入：O(L)，L = 字符串长度
• 前缀匹配：O(P)，P = 前缀长度
• 对比哈希表：空间换时间，支持前缀查询

实现 Trie（LeetCode 208）

class Trie {
    private TrieNode root = new TrieNode();

    static class TrieNode {
        TrieNode[] children = new TrieNode[26];
        boolean isEnd;
    }

    public void insert(String word) {
        TrieNode cur = root;
        for (char c : word.toCharArray()) {
            int idx = c - 'a';
            if (cur.children[idx] == null)
                cur.children[idx] = new TrieNode();
            cur = cur.children[idx];
        }
        cur.isEnd = true;
    }

    public boolean search(String word) {
        TrieNode cur = root;
        for (char c : word.toCharArray()) {
            int idx = c - 'a';
            if (cur.children[idx] == null) return false;
            cur = cur.children[idx];
        }
        return cur.isEnd;
    }

    public boolean startsWith(String prefix) {
        TrieNode cur = root;
        for (char c : prefix.toCharArray()) {
            int idx = c - 'a';
            if (cur.children[idx] == null) return false;
            cur = cur.children[idx];
        }
        return true;
    }
}

添加与搜索单词（LeetCode 211）

支持 . 通配符（匹配任意字符）。

class WordDictionary {
    private TrieNode root = new TrieNode();

    public void addWord(String word) {
        TrieNode cur = root;
        for (char c : word.toCharArray()) {
            if (cur.children[c-'a'] == null)
                cur.children[c-'a'] = new TrieNode();
            cur = cur.children[c-'a'];
        }
        cur.isEnd = true;
    }

    public boolean search(String word) {
        return dfs(word, 0, root);
    }

    private boolean dfs(String word, int idx, TrieNode node) {
        if (idx == word.length()) return node.isEnd;
        char c = word.charAt(idx);
        if (c != '.') {
            TrieNode next = node.children[c - 'a'];
            return next != null && dfs(word, idx + 1, next);
        }
        // '.' 匹配所有子节点
        for (TrieNode child : node.children) {
            if (child != null && dfs(word, idx + 1, child)) return true;
        }
        return false;
    }
}

键值映射（LeetCode 677）

Trie 中每个节点累加以该节点结尾的所有值（前缀和）。

class MapSum {
    private TrieNode root = new TrieNode();

    static class TrieNode {
        TrieNode[] children = new TrieNode[26];
        int val;
    }

    public void insert(String key, int val) {
        TrieNode cur = root;
        for (char c : key.toCharArray()) {
            if (cur.children[c-'a'] == null) cur.children[c-'a'] = new TrieNode();
            cur = cur.children[c-'a'];
        }
        cur.val = val;
    }

    public int sum(String prefix) {
        TrieNode cur = root;
        for (char c : prefix.toCharArray()) {
            if (cur.children[c-'a'] == null) return 0;
            cur = cur.children[c-'a'];
        }
        return dfsSum(cur);
    }

    private int dfsSum(TrieNode node) {
        if (node == null) return 0;
        int sum = node.val;
        for (TrieNode child : node.children) sum += dfsSum(child);
        return sum;
    }
}

删除操作（Trie 删除）

删除分三种情况：

1. 单词不存在：直接返回
2. 单词是其他单词的前缀：只取消 isEnd 标记
3. 节点无其他子节点：向上回溯删除节点

public boolean delete(String word) {
    return deleteHelper(root, word, 0);
}

private boolean deleteHelper(TrieNode node, String word, int idx) {
    if (idx == word.length()) {
        if (!node.isEnd) return false;
        node.isEnd = false;
        return isLeaf(node);    // 空叶子可删除
    }
    int ci = word.charAt(idx) - 'a';
    if (node.children[ci] == null) return false;
    boolean shouldDelete = deleteHelper(node.children[ci], word, idx + 1);
    if (shouldDelete) {
        node.children[ci] = null;
        return !node.isEnd && isLeaf(node);
    }
    return false;
}

private boolean isLeaf(TrieNode node) {
    for (TrieNode c : node.children) if (c != null) return false;
    return true;
}