【LeetCode 热题 100】208. 实现 Trie (前缀树)

Problem: 208. 实现 Trie (前缀树)

整体思路

这段代码实现了一个经典且高效的数据结构——Trie树，也被称为字典树或前缀树。Trie树是一种专门用于处理字符串集合的树形结构，它在字符串的插入、查找以及前缀匹配等操作上表现得非常高效。

该实现的整体思路如下：

1. 节点定义 (Node class)：

   • Trie树的核心是它的节点。每个节点 Node 包含两个主要部分：
     • Node[] son = new Node[26]: 一个指向子节点的指针数组。由于题目通常隐含输入为小写英文字母，所以数组大小为26。son[0] 代表字符 ‘a’，son[1] 代表 ‘b’，以此类推。如果 son[c] 为 null，表示当前节点没有通向字符 c 的路径。
     • boolean end: 一个布尔标记，用于表示从根节点到当前节点的路径是否构成一个完整的、被插入过的单词。

2. Trie树结构 (Trie class)：

   • 整个Trie树由一个根节点 root 引用来表示。根节点本身不代表任何字符，它只是所有单词路径的共同起点。

3. 核心操作实现：

   • insert(String word) - 插入单词：
     • 从根节点 root 开始，逐一处理 word 中的每个字符。
     • 对于每个字符 c，在当前节点 cur 的 son 数组中查找对应的路径。
     • 如果路径不存在 (cur.son[c] == null)，就创建一个新的 Node 并建立连接。
     • 然后，将当前节点 cur 移动到下一个节点 (cur = cur.son[c])。
     • 当单词的所有字符都处理完毕后，将最后一个节点的 end 标记设置为 true，表示一个完整单词的结束。
   • search(String word) - 查找完整单词：
     • 这个操作检查一个单词是否完整地存在于Trie树中。
     • 它通过一个私有辅助函数 find 来实现。find 函数沿着单词的字符路径在树中向下走。
     • 如果中途任何一个字符的路径不存在，说明这个单词肯定不存在，find 返回 0。
     • 如果路径走完了，find 会检查最后一个节点的 end 标记。如果 end 是 true，表示这是一个被插入过的完整单词，find 返回 1。
     • search 方法最终判断 find 的返回值是否为 1。
   • startsWith(String prefix) - 查找前缀：
     • 这个操作检查是否存在任何以给定 prefix 开头的单词。
     • 它也使用 find 函数。只要 find 函数能够成功地走完 prefix 的所有字符路径（即没有中途返回0），就说明存在以该 prefix 开头的单词。
     • find 在走完路径后，如果 end 标记为 true（是完整单词）则返回 1，如果 end 标记为 false（只是个前缀）则返回 2。
     • startsWith 方法判断 find 的返回值是否不为 0 即可。

4. find 辅助函数：

   • 这是一个巧妙的设计，它将 search 和 startsWith 的共同逻辑（即沿着路径遍历）提取了出来。
   • 通过返回三种不同的状态码（0: 不存在, 1: 是完整单词, 2: 只是前缀），它能同时服务于两个公共API，使代码更加简洁。

完整代码

class Trie {
    /**
     * 内部类，定义 Trie 树的节点结构。
     */
    private static class Node {
        // 指向子节点的指针数组，大小26，对应'a'到'z'。
        Node[] son = new Node[26];
        // 标记：从根到当前节点的路径是否构成一个完整的单词。
        boolean end; 
    }
    
    // Trie树的根节点。它不代表任何字符。
    private Node root;

    /**
     * Trie 树的构造函数。
     */
    public Trie() {
        // 初始化一个空的根节点。
        root = new Node();
    }
    
    /**
     * 向 Trie 树中插入一个单词。
     * @param word 要插入的单词
     */
    public void insert(String word) {
        // 从根节点开始遍历
        Node cur = root;
        // 逐个处理单词中的字符
        for (char c : word.toCharArray()) {
            // 将字符 'a'-'z' 映射到索引 0-25
            c -= 'a';
            // 如果通向该字符的路径不存在，则创建新节点
            if (cur.son[c] == null) {
                cur.son[c] = new Node();
            }
            // 移动到下一个节点
            cur = cur.son[c];
        }
        // 单词的所有字符都处理完毕后，将当前节点的 end 标记设为 true
        cur.end = true;
    }
    
    /**
     * 搜索一个单词是否完整地存在于 Trie 树中。
     * @param word 要搜索的单词
     * @return 如果单词存在则返回 true，否则返回 false
     */
    public boolean search(String word) {
        // 调用辅助函数 find，如果返回 1，表示找到了一个完整的单词。
        return find(word) == 1;
    }
    
    /**
     * 判断 Trie 树中是否存在以给定前缀开头的单词。
     * @param prefix 要搜索的前缀
     * @return 如果存在则返回 true，否则返回 false
     */
    public boolean startsWith(String prefix) {
        // 调用辅助函数 find，只要返回值不是 0 (路径不存在)，就说明前缀存在。
        return find(prefix) != 0;
    }

    /**
     * 私有辅助函数，用于查找一个字符串（单词或前缀）。
     * @param word 要查找的字符串
     * @return 0: 字符串路径不存在; 1: 路径存在且是一个完整单词; 2: 路径存在但只是一个前缀。
     */
    private int find(String word) {
        // 从根节点开始遍历
        Node cur = root;
        for (char c : word.toCharArray()) {
            c -= 'a';
            // 如果中途路径断了，直接返回 0
            if (cur.son[c] == null) {
                return 0; // 路径不存在
            }
            // 移动到下一个节点
            cur = cur.son[c];
        }
        // 路径走完后，根据 end 标记返回状态
        return cur.end ? 1 : 2; // 1 表示是完整单词，2 表示只是前缀
    }
}

时空复杂度

时间复杂度

令 L 为操作字符串（word 或 prefix）的长度。

• insert(word): O(L)

  • 该方法需要遍历 word 中的每一个字符。对于每个字符，它执行常数时间的操作（数组索引、判空、创建节点、指针移动）。因此，时间复杂度与字符串长度 L 成正比。

• search(word): O(L)

  • 该方法（通过 find）也需要遍历 word 中的每一个字符，在Trie树中向下移动。每个步骤都是 O(1) 的。因此，时间复杂度与字符串长度 L 成正比。

• startsWith(prefix): O(L)

  • 与 search 类似，该方法需要遍历 prefix 的所有字符，时间复杂度与前缀长度 L 成正比。

空间复杂度

令 N 为插入的所有单词的总数量，L_i 为第 i 个单词的长度。

• 空间复杂度: O(Σ L_i)
  • Trie树的空间开销主要由其节点数量决定。
  • 在最坏的情况下，如果所有插入的单词没有任何公共前缀（例如 “a”, “b”, “c”），那么每个单词的每个字符都需要创建一个新的节点。此时，总的节点数等于所有单词长度之和，即 Σ L_i。
  • 每个节点占用的空间是一个常数（一个大小为26的指针数组和一个布尔值）。
  • 因此，总的空间复杂度与所有插入单词的总字符数成正比。

总结：Trie树用空间换取了时间，它提供了与字典大小无关的、只与查询字符串长度相关的极快查询速度。

参考灵神