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 \times 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. 二叉搜索树节点最小距离下一篇