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 * 104 次

---

26叉树

Trie 前缀树，实际就是多叉树，如果只考虑小写字母那就是26叉树。

定义每个节点有一个子节点数组和一个是否结束标记。

初始化：子节点数组长度定义为26，是否结束标记定义为false 插入：将字符串中的每个字符挨个插入到树中，如果字符已存在，则看下一层，字符不存在则创建一个节点，注意：最后一个字符的节点标记为结束 查找前缀：按字符依次查找，如果返回空则未找到，全部找到为找到 查找字符串：类似查找前缀，但是结束时需要判定结束标记。

class Trie {
    vector<Trie*> chidren;
    bool isEnd;

    Trie* searchPrefix(string word) {
        Trie* node = this;
        for (auto ch : word) {
            int index = ch - 'a';
            if (node->chidren[index] == nullptr) {
                return nullptr;
            }
            node = node->chidren[index];
        }
        return node;
    }


public:
    Trie() : chidren(26), isEnd(false) {}
    
    void insert(string word) {
        Trie* node = this;
        for (auto ch : word) {
            int index = ch - 'a';
            if (node->chidren[index] == nullptr) {
                node->chidren[index] = new Trie();
            }
            node = node->chidren[index];
        }
        node->isEnd = true;

    }
    
    bool search(string word) {
        Trie* node = searchPrefix(word);
        return node != nullptr && node->isEnd;
    }
    
    bool startsWith(string prefix) {
        Trie* node = searchPrefix(prefix);
        return node != nullptr;
    }
};

/**
 * 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);
 */