Implement a trie with insert, search, and startsWith methods.
Note:
You may assume that all inputs are consist of lowercase letters a-z.

題意

實現(xiàn)一個字典樹，包含插入、查找和前綴查找功能。所有的輸入都是小寫字母a-z。

分析

就是一個正常的字典樹實現(xiàn)，每個節(jié)點包含26個指向孩子節(jié)點的指針，和標識字典中單詞結尾的isTail標識。初始化時26個指針child[i]為NULL，isTail為false。

注意

• startsWith(prefix)方法不需要待檢查的prefix是字典樹中單詞的結尾；
• search(key)方法要求待檢查key是字典樹中單詞的結尾；
• 對指針數(shù)組的聲明應該是TrieNode *child[26]。

AC代碼

class TrieNode {
public:
    // Initialize your data structure here.
    TrieNode() {
        for (int i = 0; i != 26; ++i) {
            child[i] = NULL;
            isTail = false;
        }
    }
    TrieNode *child[26];
    bool isTail;
};

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

    // Inserts a word into the trie.
    void insert(string s) {
        TrieNode *curr = root;
        for (int i = 0; i != s.size(); ++i) {
            int index = find(s[i]);
            if (!curr->child[index]) {
                curr->child[index] = new TrieNode();
            }
            curr = curr->child[index];
        }
        curr->isTail = true;
    }

    // Returns if the word is in the trie.
    bool search(string key) {
        TrieNode *curr = root;
        for (int i = 0; i != key.size(); ++i) {
            int index = find(key[i]);
            if (!curr->child[index]) return false;
            curr = curr->child[index];
        }
        if (!curr->isTail) return false;
        return true;
    }

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

private:
    TrieNode* root;
    int find(char ch) { return ch - 'a'; }
};

// Your Trie object will be instantiated and called as such:
// Trie trie;
// trie.insert("somestring");
// trie.search("key");