Leetcode 211 Solution

class TrieNode
{
public:
    TrieNode* m_children[26];
    bool m_leaf;

    TrieNode()
    {
        m_leaf = false;
        for (int i = 0; i < 26; i++)
            m_children[i] = NULL;
    }
};

class WordDictionary {
    TrieNode* root;

public:
    WordDictionary()
    {
        root = new TrieNode();
    }

    // Adds a word into the data structure.
    void addWord(string word) {
        TrieNode* nextnode = root;

        for (int i = 0; i < word.size(); i++)
        {
            char ch = word[i];

            if (nextnode->m_children[ch - 'a'] == NULL)
                nextnode->m_children[ch - 'a'] = new TrieNode();

            nextnode = nextnode->m_children[ch - 'a'];
        }

        nextnode->m_leaf = true;
    }

    bool search(const string& word, int i, TrieNode* node)
    {
        if (i == word.size())
            return node->m_leaf;

        char ch = word[i];

        if (ch == '.')
        {
            for (int j = 0; j < 26; j++)
            {
                if (node->m_children[j] && search(word, i + 1, node->m_children[j]))
                    return true;
            }

            return false;
        }
        else
        {
            if (node->m_children[ch - 'a'] == false)
                return false;

            return search(word, i + 1, node->m_children[ch - 'a']);
        }
    }

    // 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(word, 0, root);
    }
};

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