Trie (Leetcode 208 & Leetcode 21

TrieNode的建立尽量用haspmap来做，而不是array[256]。这样省空间，而且可以查找非字母(相比TrieNode *child[26])。

TrieNode比直接用hashmap存string省空间，因为大部分node都是empty，hashmap key少并不占很多内存。（考虑a，aa，aaa，aaaa这样的例子）

TrieNode和直接用hashmap存string时间一样，O(string length).

另外，Trie结构中，需要建立 TrieNode class，和 Trie class。TrieNode就是Node节点 (包含bool and hashmap)。而Trie支持add，search等功能，含有addword，searchWord等函数（像211这道题，WordDict本身就是Trie（因为含有add，search function），并不需要再建立Trie class了）

Leetcode 208:

class TrieNode {
public:
    unordered_map<char, TrieNode*> mp;
    bool isWord;
    // Initialize your data structure here.
    TrieNode() : isWord(false){}

};

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

    // Inserts a word into the trie.
    void insert(string word) {
        if(word.empty()) return;
        TrieNode *p = root;
        for(int i=0; i<word.length(); i++){
            char c = word[i];
            if(!p->mp.count(c)){
                p->mp[c] = new TrieNode();
            }
            p = p->mp[c];
        }
        p->isWord = true;
    }

    // Returns if the word is in the trie.
    bool search(string word) {
        if(word.empty()) return false;
        TrieNode *p = root;
        for(int i=0; i<word.length(); i++){
            char c = word[i];
            if(!p->mp.count(c)) return false;
            p = p->mp[c];
        }
        return p->isWord;
    }

    // Returns if there is any word in the trie
    // that starts with the given prefix.
    bool startsWith(string prefix) {
        if(prefix.empty()) return false;
        TrieNode *p = root;
        for(int i=0; i<prefix.length(); i++){
            char c = prefix[i];
            if(!p->mp.count(c)) return false;
            p = p->mp[c];
        }
        return true;
    }

private:
    TrieNode* root;
};

Leetcode 211

class TrieNode{
public:
    unordered_map<char, TrieNode*> mp;
    bool isWord;
    TrieNode() : isWord(false){}
};

class WordDictionary {
public:
    /** Initialize your data structure here. */
    WordDictionary() {
        root = new TrieNode();
    }
    
    /** Adds a word into the data structure. */
    void addWord(string word) {
        if(word.empty()){
            return;
        }
        auto *p = root;
        for(int i=0; i<word.length(); i++){
            char c = word[i];
            if(!p->mp.count(c)){
                p->mp[c] = new TrieNode();
            }
            p = p->mp[c];
        }
        p->isWord = true;
    }
    
    /** Returns if the word is in the data structure. A word could contain the dot character '.' to represent any one letter. */
    bool search(string word) {
        if(word.empty()){
            return false;
        }
        auto *p = root;
        return search_util(word, root, 0);
    }
    
    bool search_util(string word, TrieNode *p, int start){
        if(start == word.length()) return p->isWord;
        char c = word[start];
        if(c == '.'){
            for(auto it : p->mp){
                auto node = it.second;
                if(search_util(word, node, start+1)) return true;
            }
            return false;
        }
        else{
            if(!p->mp.count(c)) return false;
            return search_util(word, p->mp[c], start+1);
        }
        return false;
        
    }
private:
    TrieNode *root;
};

/**
 * Your WordDictionary object will be instantiated and called as such:
 * WordDictionary obj = new WordDictionary();
 * obj.addWord(word);
 * bool param_2 = obj.search(word);
 */