题目

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

请你实现 Trie 类：

Trie() 初始化前缀树对象。

void insert(String word) 向前缀树中插入字符串 word 。

boolean search(String word) 如果字符串 word 在前缀树中，返回 true（即，在检索之前已经插入）；否则，返回 false 。

boolean startsWith(String prefix) 如果之前已经插入的字符串 word 的前缀之一为 prefix ，返回 true ；否则，返回 false 。

来源：力扣（LeetCode）

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

解答

前缀树具体的作用，在此就不进行赘述。

直接给出节点的定义：

clase Trie {
public:
	bool isEnd;
	Trie* children[26];
}

通俗的说，前缀树就是以一个节点为单位，该单位有26个指针指向后继节点，这26个指针对应 A - Z 的26个字母。

那前缀树是如何存储单词的呢？

每个节点存储一个字母，并向后继节点延伸，每个节点有26个指针，不利于画图表示，一般当指针为空（nullptr）时，就不再表示，如下图存储了 cat 和 come 两个单词：

再来说Trie中的 isEnd，因为一个单词是有首字母和尾字母的，所以当插入的单词结束了，就在当前的节点中的 isEnd 变为真（true），这样来表示一个完整的单词。就好比cat是一个完整的单词，T 节点中的 isEnd = true，而上边的C，A节点并不为true，因为他们并没有表示一个完整的单词。

有了对节点的基本理解，insert插入单词，search查询单词操作就比较容易理解了：

1. 插入单词，就是从根节点开始，往后插入字母，（这里的字母是与a的差值，用 0-25 来表示），如果遇到要插入的字母为nullptr，就new出一个节点来即可。直到单词的尾部，进行isEnd置true。

2. 查询单词同理，从根节点开始往下查，如果根据查询单词的字母，查询到了nullptr就表示不存在，否则最后判定isEnd是否为true，进行返回即可。

代码如下：

class Trie {
public:
    bool isEnd;
    Trie *children[26];

    /** Initialize your data structure here. */
    Trie() {
        isEnd = false;
        memset(children, 0, sizeof(children));
    }

    /** Inserts a word into the trie. */
    void insert(string word) {
        auto p = this;
        for (auto i: word) {
            if (p->children[i - 'a'] == nullptr) {
                p->children[i - 'a'] = new Trie();
            }
            p = p->children[i - 'a'];
        }
        p->isEnd = true;
    }

    /** Returns if the word is in the trie. */
    bool search(string word) {
        auto p = this;
        for (auto i: word) {
            p = p->children[i - 'a'];
            if (!p) {
                return false;
            }
        }
        return p->isEnd;
    }

    /** Returns if there is any word in the trie that starts with the given prefix. */
    bool startsWith(string prefix) {
        auto p = this;
        for (auto i: prefix) {
            p = p->children[i - 'a'];
            if (!p) {
                return false;
            }
        }
        return true;
    }
};