【4.14】LeetCode每日一题·实现 Trie (前缀树)

2021年04月14日 11时07分

标签： LeetCode 树形结构 Trie树

## 题目描述
[Trie](https://baike.baidu.com/item/%E5%AD%97%E5%85%B8%E6%A0%91/9825209?fr=aladdin)（发音类似 "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 * 104 次
```

#### 来源
> 来源：力扣（LeetCode）
> 链接：[题目链接](https://leetcode-cn.com/problems/implement-trie-prefix-tree/ "题目链接")

## 解题思路
考察**Trie树（前缀树、字典树）**这一数据结构的基本概念。

**Trie**树可以在$$O(|S|)$$（$$|S|$$为每次插入或查询的字符串长度）时间内：
* 向集合中插入某一字符串；
* 查询某一字符串在集合中是否存在；
* 查询集合中是否存在包含某一前缀的字符串。

Trie树是一棵有根多叉树，其每一个节点包括两个字段：
* 指向子节点的指针数组`next[N]`，其大小`N`是字母表的大小；
* 布尔字段`end`，标记当前节点是否是某字符串的结尾。

Trie树的核心思想是，**如果两个字符串包含有相同的前缀，那么他们可以共用Trie树上的一条自顶向下的路径**。例如，考虑3个字符串`["aa", "aab", "ba"]`，构造的Trie树为：
![](https://pic.stackoverflow.wiki/uploadImages/222/190/109/123/2021/04/14/10/57/58cc9e3e-afc0-4cd5-9c38-d6cddc2a44c6.svg)

1. 插入某一字符串
	从Trie树的根开始插入字符串。检查当前字符串对应的子节点是否存在：
	* 如果存在，则移动到子节点，继续处理下一个字符；
	* 如果不存在，则创建一个新的子节点并将其连接到父节点对应的`next[]`数组上，然后移动到子节点，继续处理下一个字符。
	对于最后一个字符，将当前节点的`end`置为`True`。
2. 查找某一字符串
	从Trie树的根开始，检查当前字符串对应的子节点是否存在，如果某一节点不存在，则说明该字符串不存在；此外，如果字符串结尾在Trie树中对应的节点`end`不为`True`，也说明该字符串不存在。
3. 查找某一前缀是否存在
	和查找某一字符串操作相似，唯一区别是不用判断前缀最后一个字符对应节点的`end`是否为`True`。

## 代码
注：代码中节点的`key`数据域可以删除。
```cpp
class Trie {
private:
    static const int ALPHABET_LENGTH = 26;
    struct node{
        char key;
        bool end;
        node* next[ALPHABET_LENGTH];
        node(){
            end = false;
            fill(next, next+ALPHABET_LENGTH, nullptr);
        }
    };
    node* root;
    inline int getIndex(const char& c){
        return c - 'a';
    }
public:
    /** Initialize your data structure here. */
    Trie() {
        root = new node();
    }
    
    /** Inserts a word into the trie. */
    void insert(string word) {
        node* p = root;
        for(char& c: word){
            if(p->next[getIndex(c)]){
                p = p->next[getIndex(c)];
            }else{
                node* curr = new node();
                curr->key = c;
                p->next[getIndex(c)] = curr;
                p = p->next[getIndex(c)];
            }
        }
        p->end = true;
    }
    
    /** Returns if the word is in the trie. */
    bool search(string word) {
        node* p = root;
        for(char& c: word){
            if(p->next[getIndex(c)]){
                p = p->next[getIndex(c)];
            }else{
                return false;
            }
        }
        return p->end;
    }
    
    /** Returns if there is any word in the trie that starts with the given prefix. */
    bool startsWith(string prefix) {
        node* p = root;
        for(char& c: prefix){
            if(p->next[getIndex(c)]){
                p = p->next[getIndex(c)];
            }else{
                return false;
            }
        }
        return true;
    }
};

/**
 * Your Trie object will be instantiated and called as such:
 * Trie* obj = new Trie();
 * obj->insert(word);
 * bool param_2 = obj->search(word);
 * bool param_3 = obj->startsWith(prefix);
 */
```

## 用时和内存
> 执行用时：56 ms，在所有 C++提交中击败了93.98%的用户
> 内存消耗：43.9 MB，在所有 C++提交中击败了53.48%的用户

所有评论

暂无评论

新增评论

邮箱

邮箱仅作验证使用

图形验证码

邮箱验证码

目录

【4.14】LeetCode每日一题·实现 Trie (前缀树)

所有评论

暂无评论

新增评论