208-实现 Trie (前缀树)(Implement Trie (Prefix Tree))

原文链接: https://leetcode-cn.com/problems/implement-trie-prefix-tree

英文原文

A trie (pronounced as "try") or prefix tree is a tree data structure used to efficiently store and retrieve keys in a dataset of strings. There are various applications of this data structure, such as autocomplete and spellchecker.

Implement the Trie class:

Trie() Initializes the trie object.
void insert(String word) Inserts the string word into the trie.
boolean search(String word) Returns true if the string word is in the trie (i.e., was inserted before), and false otherwise.
boolean startsWith(String prefix) Returns true if there is a previously inserted string word that has the prefix prefix, and false otherwise.

Example 1:

Input
["Trie", "insert", "search", "search", "startsWith", "insert", "search"]
[[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]
Output
[null, null, true, false, true, null, true]

Explanation
Trie trie = new Trie();
trie.insert("apple");
trie.search("apple");   // return True
trie.search("app");     // return False
trie.startsWith("app"); // return True
trie.insert("app");
trie.search("app");     // return True

Constraints:

1 <= word.length, prefix.length <= 2000
word and prefix consist only of lowercase English letters.
At most 3 * 10⁴ calls in total will be made to insert, search, and startsWith.

中文题目

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⁴ 次

通过代码

高赞题解

Trie [traɪ] 读音和 try 相同，它的另一些名字有：字典树，前缀树，单词查找树等。

介绍 Trie🌳

Trie 是一颗非典型的多叉树模型，多叉好理解，即每个结点的分支数量可能为多个。

为什么说非典型呢？因为它和一般的多叉树不一样，尤其在结点的数据结构设计上，比如一般的多叉树的结点是这样的：

[]

struct TreeNode {

    VALUETYPE value;    //结点值

    TreeNode* children[NUM];    //指向孩子结点

};

而 Trie 的结点是这样的(假设只包含’a’~’z’中的字符)：

[]

struct TrieNode {

    bool isEnd; //该结点是否是一个串的结束

    TrieNode* next[26]; //字母映射表

};

要想学会 Trie 就得先明白它的结点设计。我们可以看到TrieNode结点中并没有直接保存字符值的数据成员，那它是怎么保存字符的呢？

这时字母映射表next 的妙用就体现了，TrieNode* next[26]中保存了对当前结点而言下一个可能出现的所有字符的链接，因此我们可以通过一个父结点来预知它所有子结点的值：

[]

for (int i = 0; i < 26; i++) {

    char ch = 'a' + i;

    if (parentNode->next[i] == NULL) {

        说明父结点的后一个字母不可为 ch

    } else {

        说明父结点的后一个字母可以是 ch

    }

}

我们来看个例子吧。

想象以下，包含三个单词 “sea”,”sells”,”she” 的 Trie 会长啥样呢？

它的真实情况是这样的：

Trie 中一般都含有大量的空链接，因此在绘制一棵单词查找树时一般会忽略空链接，同时为了方便理解我们可以画成这样：

接下来我们一起来实现对 Trie 的一些常用操作方法。

定义类 Trie

[]

class Trie {

private:

    bool isEnd;

    Trie* next[26];

public:

    //方法将在下文实现...

};

插入

描述：向 Trie 中插入一个单词 word

实现：这个操作和构建链表很像。首先从根结点的子结点开始与 word 第一个字符进行匹配，一直匹配到前缀链上没有对应的字符，这时开始不断开辟新的结点，直到插入完 word 的最后一个字符，同时还要将最后一个结点isEnd = true;，表示它是一个单词的末尾。

[]

void insert(string word) {

    Trie* node = this;

    for (char c : word) {

        if (node->next[c-'a'] == NULL) {

            node->next[c-'a'] = new Trie();

        }

        node = node->next[c-'a'];

    }

    node->isEnd = true;

}

查找

描述：查找 Trie 中是否存在单词 word

实现：从根结点的子结点开始，一直向下匹配即可，如果出现结点值为空就返回 false，如果匹配到了最后一个字符，那我们只需判断 node->isEnd即可。

[]

bool search(string word) {

    Trie* node = this;

    for (char c : word) {

        node = node->next[c - 'a'];

        if (node == NULL) {

            return false;

        }

    }

    return node->isEnd;

}

前缀匹配

描述：判断 Trie 中是或有以 prefix 为前缀的单词

实现：和 search 操作类似，只是不需要判断最后一个字符结点的isEnd，因为既然能匹配到最后一个字符，那后面一定有单词是以它为前缀的。

[]

bool startsWith(string prefix) {

    Trie* node = this;

    for (char c : prefix) {

        node = node->next[c-'a'];

        if (node == NULL) {

            return false;

        }

    }

    return true;

}

到这我们就已经实现了对 Trie 的一些基本操作，这样我们对 Trie 就有了进一步的理解。完整代码我贴在了文末。

总结

通过以上介绍和代码实现我们可以总结出 Trie 的几点性质：

Trie 的形状和单词的插入或删除顺序无关，也就是说对于任意给定的一组单词，Trie 的形状都是唯一的。

查找或插入一个长度为 L 的单词，访问 next 数组的次数最多为 L+1，和 Trie 中包含多少个单词无关。

Trie 的每个结点中都保留着一个字母表，这是很耗费空间的。如果 Trie 的高度为 n，字母表的大小为 m，最坏的情况是 Trie 中还不存在前缀相同的单词，那空间复杂度就为 $O(m^n)$。

最后，关于 Trie 的应用场景，希望你能记住 8 个字：一次建树，多次查询。(慢慢领悟叭~~)

全部代码

[]

class Trie {

private:

    bool isEnd;

    Trie* next[26];

public:

    Trie() {

        isEnd = false;

        memset(next, 0, sizeof(next));

    }

    

    void insert(string word) {

        Trie* node = this;

        for (char c : word) {

            if (node->next[c-'a'] == NULL) {

                node->next[c-'a'] = new Trie();

            }

            node = node->next[c-'a'];

        }

        node->isEnd = true;

    }

    

    bool search(string word) {

        Trie* node = this;

        for (char c : word) {

            node = node->next[c - 'a'];

            if (node == NULL) {

                return false;

            }

        }

        return node->isEnd;

    }

    

    bool startsWith(string prefix) {

        Trie* node = this;

        for (char c : prefix) {

            node = node->next[c-'a'];

            if (node == NULL) {

                return false;

            }

        }

        return true;

    }

};

最后

至此，您已经掌握了 Trie 树的实现以及对它的一些基本操作，感谢您的观看！

统计信息

通过次数	提交次数	AC比率
156090	217518	71.8%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言

相似题目

题目	难度
添加与搜索单词 - 数据结构设计	中等
设计搜索自动补全系统	困难
单词替换	中等
实现一个魔法字典	中等

凤起丶宛南

从来没有真正的绝境，只有心灵的迷途