面试速答（先看这里）

**一句话结论：**前缀树（Trie，又称字典树或键树）是一种树形结构，它是一种用于快速检索字符串集合中字符串的高效数据结构。

60秒标准回答：

前缀树（Trie，又称字典树或键树）是一种树形结构，它是一种用于快速检索字符串集合中字符串的高效数据结构。前缀树的每个节点代表一个字符串（或字符串的一部分），从根节点到某一节点的路径上经过的字符连接起来，就是该节点对应的字符串

前缀树的特点

举个例子：有以下字符串

**答题顺序：**结论 → 原理/机制 → 关键流程 → 场景与取舍 → 易错点

回答主线：

• **前缀树有哪些应用？：**给出N 个单词组成的熟词表，以及一篇全用小写英文书写的文章，请你按最早出现的顺序写出所有不在熟词表中的生词。
• **字符串最长公共前缀：**给出N 个小写英文字母串，以及Q 个询问，即询问某两个串的最长公共前缀的长度是多少？
• **作为其他数据结构和算法的辅助结构：**trie树在这里的应用类似哈夫曼树，比如词频统计使用哈希表或者堆都可以，但是如果内存有限，就可以用trie树来压缩空间，因为trie树的公共前缀都是用一个节点保存的。
• **字符串搜索的前缀匹配：**trie树常用于搜索提示。

**记忆锚点：**trie → 前缀树 → Trie → 字典树 → 作为其他数据结构和算法的辅助结构 → 于快速检索字符串集合

加分表达：

• 举个例子：有以下字符串： abc,bac,bbc,ca， 通过字典树形成的结构如下所示： 从上图我们可以看出，通过字典树，在查询的时候，原来的时间复杂度是O(n*m)，优化后的时间复杂度就会变成O(m)。
• 同时，如果有很多字符串，字典树还可以大大减少存储的空间。
• Trie树是一棵多叉树，只要先序遍历整棵树，输出相应的字符串便是按字典序排序的结果。

追问准备：

• 字典树的java实现如下所示： 前缀树有哪些应用？
• 字符串最长公共前缀 给出N 个小写英文字母串，以及Q 个询问，即询问某两个串的最长公共前缀的长度是多少？

---

典型回答

前缀树（Trie，又称字典树或键树）是一种树形结构，它是一种用于快速检索字符串集合中字符串的高效数据结构。前缀树的每个节点代表一个字符串（或字符串的一部分），从根节点到某一节点的路径上经过的字符连接起来，就是该节点对应的字符串。

前缀树的特点：

• 根节点不包含字符，除根节点外的每个节点都只包含一个字符。
• 从根节点到某一节点的路径上经过的字符连接起来，为该节点对应的字符串。
• 每个节点的所有子节点包含的字符都不相同。

举个例子：有以下字符串：

abc,bac,bbc,ca，

通过字典树形成的结构如下所示：

从上图我们可以看出，通过字典树，在查询的时候，原来的时间复杂度是O(n*m)，优化后的时间复杂度就会变成O(m)。同时，如果有很多字符串，字典树还可以大大减少存储的空间。

字典树的java实现如下所示：

class Trie {

    private Trie[] children;

    private boolean isWord;

    public Trie() {
        this.isWord = false;
        this.children = new Trie[26];
    }
    
    public void insert(String word) {
        Trie next = this;
        for(char c : word.toCharArray()) {
            if(next.children[c - 'a'] == null) {
                next.children[c - 'a'] = new Trie();
            }
            next = next.children[c - 'a'];
        }
        next.isWord = true;
    }
    
    public boolean search(String word) {
        Trie next = this;
        for(char c : word.toCharArray()) {
            if(next.children[c - 'a'] == null) {
                return false;
            }
            next = next.children[c - 'a'];
        }
        return next.isWord;
    }
    
    public boolean startsWith(String prefix) {
        Trie next = this;
        for(char c : prefix.toCharArray()) {
            if(next.children[c - 'a'] == null) {
                return false;
            }
            next = next.children[c - 'a'];
        }
        return true;
    }
}

知识扩展

前缀树有哪些应用？

字符串检索

给出N 个单词组成的熟词表，以及一篇全用小写英文书写的文章，请你按最早出现的顺序写出所有不在熟词表中的生词。

字符串最长公共前缀

给出N 个小写英文字母串，以及Q 个询问，即询问某两个串的最长公共前缀的长度是多少？

排序

Trie树是一棵多叉树，只要先序遍历整棵树，输出相应的字符串便是按字典序排序的结果。比如给你N 个互不相同的仅由一个单词构成的英文名，让你将它们按字典序从小到大排序输出。

作为其他数据结构和算法的辅助结构

如后缀树，AC自动机等

词频统计

trie树在这里的应用类似哈夫曼树，比如词频统计使用哈希表或者堆都可以，但是如果内存有限，就可以用trie树来压缩空间，因为trie树的公共前缀都是用一个节点保存的。

字符串搜索的前缀匹配

trie树常用于搜索提示。如当输入一个网址，可以自动搜索出可能的选择。当没有完全匹配的搜索结果，可以返回前缀最相似的可能。