实现 Trie

数据结构之Trie树
Trie树：应用于统计和排序

实现一个 Trie，包含 insert, search, 和 startsWith 这三个方法。

 注意事项

你可以假设所有的输入都是小写字母a-z。

您在真实的面试中是否遇到过这个题？ Yes
样例
insert("lintcode")
search("code") // return false
startsWith("lint") // return true
startsWith("linterror") // return false
insert("linterror")
search("lintcode) // return true
startsWith("linterror") // return true

/**
 * Your Trie object will be instantiated and called as such:
 * Trie trie;
 * trie.insert("lintcode");
 * trie.search("lint"); will return false
 * trie.startsWith("lint"); will return true
 */
class TrieNode {
public:
    // Initialize your data structure here.
    bool isWord = false;
    TrieNode *child[26];
    TrieNode() {
        memset(child, 0, sizeof(child));
    }
};

class Trie {
public:
    Trie() {
        root = new TrieNode();
    }

    // Inserts a word into the trie.
    void insert(string word) {
        TrieNode *pt = root;
        int len = word.size();
        for(int i = 0;i < len;i++) {
            int index = word[i] - 'a';
            if(pt->child[index] == NULL) pt->child[index] = new TrieNode();
           pt = pt->child[index];
        }
        pt->isWord = true;
    }

    // Returns if the word is in the trie.
    bool search(string word) {
        int len = word.size();
        TrieNode* pt = root;
        for(int i = 0;i < len;i++) {
            int index = word[i] - 'a';
            if(pt->child[index] == NULL) return false;
            else {
                pt = pt->child[index];
            }
        }
        return pt->isWord;
    }

    // Returns if there is any word in the trie
    // that starts with the given prefix.
    bool startsWith(string prefix) {
         int len = prefix.size();
        TrieNode* pt = root;
        for(int i = 0;i < len;i++) {
            int index = prefix[i] - 'a';
            if(pt->child[index] == NULL) return false;
            else {
                pt = pt->child[index];
            }
        }
        return true;
    }

private:
    TrieNode* root;
};