# Leetcode 208 Solution

This article provides solution to leetcode question 208 (implement-trie-prefix-tree)

https://leetcode.com/problems/implement-trie-prefix-tree

## Solution

``````class TrieNode {
public:
TrieNode* m_children[26] = {0};
bool m_leaf = false;
};

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

// Inserts a word into the trie.
void insert(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;
}

// Returns if the word is in the trie.
bool search(string word) {
TrieNode* nextnode = root;

for (int i = 0; i < word.size(); i++)
{
char ch = word[i];
if (nextnode->m_children[ch - 'a'] == NULL)
return false;
nextnode = nextnode->m_children[ch - 'a'];
}

return nextnode->m_leaf;
}

// Returns if there is any word in the trie
// that starts with the given prefix.
bool startsWith(string prefix) {
TrieNode* nextnode = root;

for (int i = 0; i < prefix.size(); i++)
{
char ch = prefix[i];
if (nextnode->m_children[ch - 'a'] == NULL)
return false;
nextnode = nextnode->m_children[ch - 'a'];
}

return true;
}

private:
TrieNode* root;
};

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