原题链接
    Implement a trie with insert, search, and startsWith methods.

    Example:

    1. Trie trie = new Trie();
    2. trie.insert("apple");
    3. trie.search("apple");   // returns true
    4. trie.search("app");     // returns false
    5. trie.startsWith("app"); // returns true
    6. trie.insert("app");   
    7. trie.search("app");     // returns true

    Note:

    You may assume that all inputs are consist of lowercase letters a-z.
    All inputs are guaranteed to be non-empty strings.

    image.png

    1. class Trie {
    2. private:
    3.     bool isEnd;
    4.     Trie* next[26];
    5. public:
    6.     Trie() {
    7.         isEnd = false;
    8.         memset(next, 0, sizeof(next));
    9.     }
    11.     void insert(string word) {
    12.         Trie* node = this;
    13.         for (char c : word) {
    14.             if (node->next[c-'a'] == NULL) {
    15.                 node->next[c-'a'] = new Trie();
    16.             }
    17.             node = node->next[c-'a'];
    18.         }
    19.         node->isEnd = true;
    20.     }
    22.     bool search(string word) {
    23.         Trie* node = this;
    24.         for (char c : word) {
    25.             node = node->next[c - 'a'];
    26.             if (node == NULL) {
    27.                 return false;
    28.             }
    29.         }
    30.         return node->isEnd;
    31.     }
    33.     bool startsWith(string prefix) {
    34.         Trie* node = this;
    35.         for (char c : prefix) {
    36.             node = node->next[c-'a'];
    37.             if (node == NULL) {
    38.                 return false;
    39.             }
    40.         }
    41.         return true;
    42.     }
    43. };