Design Add and Search Words Data Structure Solutions in C++

// Source : https://leetcode.com/problems/add-and-search-word-data-structure-design/
// Author : Hao Chen
// Date   : 2015-06-10


#include <string.h>
#include <iostream>
#include <string>
using namespace std;

const int MAX_CHARS = 26;

/*Trie Node*/
class TrieNode {
public:
    TrieNode():isWord(false) {
        memset(childern, 0, sizeof(childern));
    }
    TrieNode* & operator [] (char idx){
        int i = (idx-'a') % MAX_CHARS;
        return childern[i];
    }
    TrieNode* & operator [] (int idx){
        int i = idx % MAX_CHARS;
        return childern[i];
    }
    bool isWord;
private:
    TrieNode* childern[MAX_CHARS];
};


/*Trie Tree*/
class TrieTree {
public:
    TrieTree():root(new TrieNode()){ }
    ~TrieTree() { freeTree(root); }
    
    void put(string &s) {
        TrieNode* node = root;
        for (int i=0; i<s.size(); i++){
            if ((*node)[s[i]] == NULL){
                (*node)[s[i]] = new TrieNode();
            }
            node = (*node)[s[i]];
        }
        node->isWord = true;
    }
    bool search(string &s){
        return get(s, this->root);
    }

private:

    bool get(string &s, TrieNode* root, int idx=0){
        TrieNode* node = root;
        for (int i=idx; i<s.size(); i++){
            if (s[i]!='.'){
                node = (*node)[s[i]];
                if (node == NULL) return false;
            }else{
                for (int j=0; j<MAX_CHARS; j++) {
                    TrieNode *p = (*node)[j];
                    if (p == NULL ) {
                        continue;//try next
                    }
                    // p!=NULL
                    if (i<s.size()-1) {
                        if (this->get(s, p, i+1)) {
                            return true;
                        }
                        continue; //try next
                    }
                    // p!=NULL && i == s.size()-1
                    if (p->isWord) {
                        return true;
                    }
                }
                return false;
            }
        }
        return node->isWord; 
    }
    
private:
    void freeTree(TrieNode* root){
        for(int i=0; i<MAX_CHARS; i++){
            if ((*root)[i]!=NULL){
                freeTree((*root)[i]);
            }
        }
        delete root;
    }
    TrieNode *root;
};

class WordDictionary {
public:

    // Adds a word into the data structure.
    void addWord(string word) {
        tree.put(word);
    }

    // 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) {
        return tree.search(word);
    }
private:
    TrieTree tree;
};

// Your WordDictionary object will be instantiated and called as such:
// WordDictionary wordDictionary;
// wordDictionary.addWord("word");
// wordDictionary.search("pattern");

int main()
{
    WordDictionary wd;
    wd.addWord("a");
    cout << wd.search("a.") <<endl;;
    cout << wd.search(".a") << endl;;
    wd.addWord("bad");
    cout << wd.search("bad") <<endl;;
    cout << wd.search("b..") <<endl;;
    return 0;
}

/// Source : https://leetcode.com/problems/add-and-search-word-data-structure-design/description/
/// Author : liuyubobobo
/// Time   : 2017-11-10

#include <iostream>
#include <map>
#include <vector>

using namespace std;

/// Trie
/// Time Complexity: addWord: O(len(word))
///                  search:  O(size(trie))
/// Space Complexity: O(sum(len(wi))) where wi is the length of the ith word
class WordDictionary {

private:
    struct Node {
        map<char, int> next;
        bool end = false;
    };
    vector<Node> trie;

public:
    /** Initialize your data structure here. */
    WordDictionary() {
        trie.clear();
        trie.push_back(Node());
    }

    /** Adds a word into the data structure. */
    void addWord(string word) {
        int treeID = 0;
        for(char c: word){
            if(trie[treeID].next.find(c) == trie[treeID].next.end()){
                trie[treeID].next[c] = trie.size();
                trie.push_back(Node());
            }

            treeID = trie[treeID].next[c];
        }

        trie[treeID].end = 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) {
        return search(0, word, 0);
    }

private:
    bool search(int treeID, const string &word, int index) {

        if (index == word.size())
            return trie[treeID].end;

        if(word[index] != '.'){
            if (trie[treeID].next.find(word[index]) == trie[treeID].next.end())
                return false;

            return search(trie[treeID].next[word[index]], word, index + 1);
        }
        else{
            for(pair<char, int> next: trie[treeID].next)
                if(search(next.second, word, index + 1))
                    return true;
            return false;
        }
    }
};


void printBool(bool res){
    cout << (res ? "True" : "False") << endl;
}

int main() {

    WordDictionary obj;
    obj.addWord("bad");
    obj.addWord("mad");
    obj.addWord("dad");
    printBool(obj.search("pad")); // false
    printBool(obj.search("bad")); // true
    printBool(obj.search(".ad")); // true
    printBool(obj.search("b..")); // true

    return 0;
}