## # 208. Implement Trie (Prefix Tree)

Implement a trie with insert, search, and startsWith methods.

Example:

``````Trie trie = new Trie();

trie.insert("apple");
trie.search("apple");   // returns true
trie.search("app");     // returns false
trie.startsWith("app"); // returns true
trie.insert("app");
trie.search("app");     // returns true
``````

Note:

• You may assume that all inputs are consist of lowercase letters a-z.
• All inputs are guaranteed to be non-empty strings.

### # Solution

Approach 1: a trie (prefix tree) has an empty root node. Each subsequent node contains only 1 character.

### # Code (Python)

Approach 1:

``````class TrieNode:

def __init__(self):
self.is_word = False
self.children = {} # can also use an array of 26 chars

class Trie:

def __init__(self):
"""
"""
self._root = TrieNode()

def insert(self, word: 'str') -> 'None':
"""
Inserts a word into the trie.
"""
cur = self._root
for char in word:
if char not in cur.children:
cur.children[char] = TrieNode()
cur = cur.children[char]
cur.is_word = True

def search(self, word: 'str') -> 'bool':
"""
Returns if the word is in the trie.
"""
cur = self._root
for char in word:
if char not in cur.children:
return False
cur = cur.children[char]
return cur.is_word

def startsWith(self, prefix: 'str') -> 'bool':
"""
Returns if there is any word in the trie that starts with the given prefix.
"""
cur = self._root
for char in prefix:
if char not in cur.children:
return False
cur = cur.children[char]
return True
``````

### # Code (C++)

Approach 1:

``````class TrieNode {
public:
TrieNode *children[26];
bool isEnd;
TrieNode() {
for (int i = 0; i < 26; ++i)
{
children[i] = NULL;
}
isEnd = false;
}
};

class Trie {
private:
TrieNode *root;
public:
/** Initialize your data structure here. */
Trie() {
root = new TrieNode();
}

/** Inserts a word into the trie. */
void insert(string word) {
TrieNode *node = root;
for (int i = 0; i < word.size(); ++i)
{
int letterIdx = word[i] - 'a';
if (node->children[letterIdx] == NULL)
{
node->children[letterIdx] = new TrieNode();
}
node = node->children[letterIdx];
}
node->isEnd = true;
}

/** Returns if the word is in the trie. */
bool search(string word) {
TrieNode *node = root;
for (int i = 0; i < word.size(); ++i)
{
int letterIdx = word[i] - 'a';
if (node->children[letterIdx] == NULL)
{
return false;
}
node = node->children[letterIdx];
}
return node->isEnd;
}

/** Returns if there is any word in the trie that starts with the given prefix. */
bool startsWith(string prefix) {
TrieNode *node = root;
for (int i = 0; i < prefix.size(); ++i)
{
int letterIdx = prefix[i] - 'a';
if (node->children[letterIdx] == NULL)
{
return false;
}
node = node->children[letterIdx];
}
return true;
}
};

/**
* Your Trie object will be instantiated and called as such:
* Trie* obj = new Trie();
* obj->insert(word);
* bool param_2 = obj->search(word);
* bool param_3 = obj->startsWith(prefix);
*/
``````