# Leetcode 211 Solution

## 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.
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;