LC 208. 实现 Trie (前缀树)

题目描述

这是 LeetCode 上的 208. 实现 Trie (前缀树) ，难度为中等。

Tag :「字典树」

Trie（发音类似 “try”）或者说前缀树是一种树形数据结构，用于高效地存储和检索字符串数据集中的键。这一数据结构有相当多的应用情景，例如自动补完和拼写检查。

请你实现 Trie 类：

Trie() 初始化前缀树对象。
void insert(String word) 向前缀树中插入字符串 word 。
boolean search(String word) 如果字符串 word 在前缀树中，返回 true（即，在检索之前已经插入）；否则，返回 false 。
boolean startsWith(String prefix) 如果之前已经插入的字符串 word 的前缀之一为 prefix ，返回 true ；否则，返回 false 。

示例：

输入
["Trie", "insert", "search", "search", "startsWith", "insert", "search"]
[[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]

输出
[null, null, true, false, true, null, true]

解释
Trie trie = new Trie();
trie.insert("apple");
trie.search("apple");   // 返回 True
trie.search("app");     // 返回 False
trie.startsWith("app"); // 返回 True
trie.insert("app");
trie.search("app");     // 返回 True

提示：

1 <= word.length, prefix.length <= 2000
word 和 prefix 仅由小写英文字母组成
insert、search 和 startsWith 调用次数总计不超过 3 * $10^4$ 次

Trie 树

$Trie$ 树（又叫「前缀树」或「字典树」）是一种用于快速查询「某个字符串/字符前缀」是否存在的数据结构。

其核心是使用「边」来代表有无字符，使用「点」来记录是否为「单词结尾」以及「其后续字符串的字符是什么」。

（中等）/image_0.png)

二维数组

一个朴素的想法是直接使用「二维数组」来实现 $Trie$ 树。

使用二维数组 $trie[]$ 来存储我们所有的单词字符。
使用 $index$ 来自增记录我们到底用了多少个格子（相当于给被用到格子进行编号）。
使用 $count[]$ 数组记录某个格子被「被标记为结尾的次数」（当 $idx$ 编号的格子被标记了 $n$ 次，则有 $cnt[idx] = n$）。

代码：

[]

class Trie {
    int N = 100009; // 直接设置为十万级
    int[][] trie;
    int[] count;
    int index;

    public Trie() {
        trie = new int[N][26];
        count = new int[N];
        index = 0;
    }
    
    public void insert(String s) {
        int p = 0;
        for (int i = 0; i < s.length(); i++) {
            int u = s.charAt(i) - 'a';
            if (trie[p][u] == 0) trie[p][u] = ++index;
            p = trie[p][u];
        }
        count[p]++;
    }
    
    public boolean search(String s) {
        int p = 0;
        for (int i = 0; i < s.length(); i++) {
            int u = s.charAt(i) - 'a';
            if (trie[p][u] == 0) return false;
            p = trie[p][u];
        }
        return count[p] != 0;
    }
    
    public boolean startsWith(String s) {
        int p = 0;
        for (int i = 0; i < s.length(); i++) {
            int u = s.charAt(i) - 'a';
            if (trie[p][u] == 0) return false;
            p = trie[p][u];
        }
        return true;
    }
}

时间复杂度：$Trie$ 树的每次调用时间复杂度取决于入参字符串的长度。复杂度为 $O(Len)$。
空间复杂度：二维数组的高度为 $n$，字符集大小为 $k$。复杂度为 $O(nk)$。

TrieNode

相比二维数组，更加常规的做法是建立 $TrieNode$ 结构节点。

随着数据的不断插入，根据需要不断创建 $TrieNode$ 节点。

代码：

[]

class Trie {
    class TrieNode {
        boolean end;
        TrieNode[] tns = new TrieNode[26];
    }

    TrieNode root;
    public Trie() {
        root = new TrieNode();
    }

    public void insert(String s) {
        TrieNode p = root;
        for(int i = 0; i < s.length(); i++) {
            int u = s.charAt(i) - 'a';
            if (p.tns[u] == null) p.tns[u] = new TrieNode();
            p = p.tns[u]; 
        }
        p.end = true;
    }

    public boolean search(String s) {
        TrieNode p = root;
        for(int i = 0; i < s.length(); i++) {
            int u = s.charAt(i) - 'a';
            if (p.tns[u] == null) return false;
            p = p.tns[u]; 
        }
        return p.end;
    }

    public boolean startsWith(String s) {
        TrieNode p = root;
        for(int i = 0; i < s.length(); i++) {
            int u = s.charAt(i) - 'a';
            if (p.tns[u] == null) return false;
            p = p.tns[u]; 
        }
        return true;
    }
}

时间复杂度：$Trie$ 树的每次调用时间复杂度取决于入参字符串的长度。复杂度为 $O(Len)$。
空间复杂度：结点数量为 $n$，字符集大小为 $k$。复杂度为 $O(nk)$。

两种方式的对比

使用「二维数组」的好处是写起来飞快，同时没有频繁 $new$ 对象的开销。但是需要根据数据结构范围估算我们的「二维数组」应该开多少行。

坏处是使用的空间通常是「$TrieNode$」方式的数倍，而且由于通常对行的估算会很大，导致使用的二维数组开得很大，如果这时候每次创建 $Trie$ 对象时都去创建数组的话，会比较慢，而且当样例多的时候甚至会触发 $GC$（因为 $OJ$ 每测试一个样例会创建一个 $Trie$ 对象）。

因此还有一个小技巧是将使用到的数组转为静态，然后利用 $index$ 自增的特性在初始化 $Trie$ 时执行清理工作 & 重置逻辑。

这样的做法能够使评测时间降低一半，运气好的话可以得到一个与「$TrieNode$」方式差不多的时间。

[]

class Trie {
    // 以下 static 成员独一份，被创建的多个 Trie 共用
    static int N = 100009; // 直接设置为十万级
    static int[][] trie = new int[N][26];
    static int[] count = new int[N];
    static int index = 0;

    // 在构造方法中完成重置 static 成员数组的操作
    // 这样做的目的是为减少 new 操作（无论有多少测试数据，上述 static 成员只会被 new 一次）
    public Trie() {
        for (int row = index; row >= 0; row--) {
            Arrays.fill(trie[row], 0);
        }
        Arrays.fill(count, 0);
        index = 0;
    }
    
    public void insert(String s) {
        int p = 0;
        for (int i = 0; i < s.length(); i++) {
            int u = s.charAt(i) - 'a';
            if (trie[p][u] == 0) trie[p][u] = ++index;
            p = trie[p][u];
        }
        count[p]++;
    }
    
    public boolean search(String s) {
        int p = 0;
        for (int i = 0; i < s.length(); i++) {
            int u = s.charAt(i) - 'a';
            if (trie[p][u] == 0) return false;
            p = trie[p][u];
        }
        return count[p] != 0;
    }
    
    public boolean startsWith(String s) {
        int p = 0;
        for (int i = 0; i < s.length(); i++) {
            int u = s.charAt(i) - 'a';
            if (trie[p][u] == 0) return false;
            p = trie[p][u];
        }
        return true;
    }
}

关于「二维数组」是如何工作 & 1e5 大小的估算

要搞懂为什么行数估算是 1e5，首先要搞清楚「二维数组」是如何工作的。

在「二维数组」中，我们是通过 $index$ 自增来控制使用了多少行的。

当我们有一个新的字符需要记录，我们会将 $index$ 自增（代表用到了新的一行），然后将这新行的下标记录到当前某个前缀的格子中。

举个🌰，假设我们先插入字符串 abc 这时候，前面三行会被占掉。

第 0 行 a 所对应的下标有值，值为 1，代表前缀 a 后面接的字符串会被记录在下标为 1 的行内
第 1 行 b 所对应的下标有值，值为 2，代表前缀 ab 后面接的字符串会被记录在下标为 2 的行内
第 2 行 c 所对应的下标有值，值为 3，代表前缀 abc 后面接的字符串会被记录在下标为 3 的行内

当再插入 abcl 的时候，这时候会先定位到 abl 的前缀行（第 3 行），将 l 的下标更新为 4，代表 abcl 被加入前缀树，并且前缀 abcl 接下来会用到第 4 行进行记录。

但当插入 abl 的时候，则会定位到 ab 的前缀行（第 2 行），然后将 l 的下标更新为 5，代表 abl 被加入前缀树，并且前缀 abl 接下来会使用第 5 行进行记录。

当搞清楚了「二维数组」是如何工作之后，我们就能开始估算会用到多少行了，调用次数为 $10^4$，传入的字符串长度为 $10^3$，假设每一次的调用都是 $insert$，并且每一次调用都会使用到新的 $10^3$ 行。那么我们的行数需要开到 $10^7$。

但由于我们的字符集大小只有 26，因此不太可能在 $10^4$ 次调用中都用到新的 $10^3$ 行。

而且正常的测试数据应该是 $search$ 和 $startsWith$ 调用次数大于 $insert$ 才有意义的，一个只有 $insert$ 调用的测试数据，任何实现方案都能 AC。

因此我设定了 $10^5$ 为行数估算，当然直接开到 $10^6$ 也没有问题。

关于 Trie 的应用面

首先，在纯算法领域，前缀树算是一种较为常用的数据结构。

不过如果在工程中，不考虑前缀匹配的话，基本上使用 hash 就能满足。

如果考虑前缀匹配的话，工程也不会使用 Trie 。

一方面是字符集大小不好确定（题目只考虑 26 个字母，字符集大小限制在较小的 26 内）因此可以使用 Trie，但是工程一般兼容各种字符集，一旦字符集大小很大的话，Trie 将会带来很大的空间浪费。

另外，对于个别的超长字符 Trie 会进一步变深。

这时候如果 Trie 是存储在硬盘中，Trie 结构过深带来的影响是多次随机 IO，随机 IO 是成本很高的操作。

同时 Trie 的特殊结构，也会为分布式存储将会带来困难。

因此在工程领域中 Trie 的应用面不广。

至于一些诸如「联想输入」、「模糊匹配」、「全文检索」的典型场景在工程主要是通过 ES (ElasticSearch) 解决的。

而 ES 的实现则主要是依靠「倒排索引」

最后

这是我们「刷穿 LeetCode」系列文章的第 No.208 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode 。

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议，转载请注明出处！

LC 213. 打家劫舍 II 上一篇

LC 783. 二叉搜索树节点最小距离下一篇