1. 插入一个字符串
    2. 查找字符串
    3. 查找是否字符串前缀
    4. 两种查找区别在于：是否isEnd
    5. 一次建树，多次查询
    1. class Trie {
    2. private:
    3.     vector<Trie *> children;
    4.     bool isEnd;
    5. public:
    6.     /** Initialize your data structure here. */
    7.     Trie() {
    8.         children.resize(26, nullptr);
    9.         isEnd = false;
    10.     }
    12.     /** Inserts a word into the trie. */
    13.     void insert(string word) {
    14.         Trie *node = this;
    15.         for (int i = 0; i < word.size(); i++) {
    16.             int ch = word[i] - 'a';
    17.             if (node->children[ch] == nullptr) {
    18.                 node->children[ch] = new Trie();
    19.             } 
    20.             node = node->children[ch];
    21.         }
    22.         node->isEnd = true;
    23.     }
    25.     /** Returns if the word is in the trie. */
    26.     bool search(string word) {
    27.         Trie *node = this;
    28.         for (int i = 0; i < word.size(); i++) {
    29.             int ch = word[i] - 'a';
    30.             if (node->children[ch] == nullptr) {
    31.                 return false;
    32.             }
    33.             node = node->children[ch];
    34.         }
    35.         return (node != nullptr && node->isEnd);
    36.     }
    38.     /** Returns if there is any word in the trie that starts with the given prefix. */
    39.     bool startsWith(string prefix) {
    40.         Trie *node = this;
    41.         for (int i = 0; i < prefix.size(); i++) {
    42.             int ch = prefix[i] - 'a';
    43.             if (node->children[ch] == nullptr) {
    44.                 return false;
    45.             }
    46.             node = node->children[ch];
    47.         }
    48.         return (node != nullptr);
    49.     }
    50. };
    52. /**
    53.  * Your Trie object will be instantiated and called as such:
    54.  * Trie* obj = new Trie();
    55.  * obj->insert(word);
    56.  * bool param_2 = obj->search(word);
    57.  * bool param_3 = obj->startsWith(prefix);
    58.  */