# 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):
"""
Initialize your data structure here.
"""
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);
*/