# LeetCode 208. Implement Trie (Prefix Tree)

## Description

https://leetcode.com/problems/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.

## Explanation

One key step is to implement TrieNode correctly. Each TrieNode represents a character and holds a dictionary field “children” which maps the next adjacent characters to their Trie Nodes. Additionally, there is an “is_word” boolean field associates with each trie node to indicate whether the string is a word.

## Python Solution

``````class TrieNode:
def __init__(self):
self.children = {}
self.is_word = False

class Trie:

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

def insert(self, word: str) -> None:
"""
Inserts a word into the trie.
"""
node = self.root

for ch in word:
if ch not in node.children:
node.children[ch] = TrieNode()
node = node.children[ch]
else:
node = node.children[ch]

node.is_word = True

def search(self, word: str) -> bool:
"""
Returns if the word is in the trie.
"""
node = self.root

for ch in word:
if ch not in node.children:
return False
else:
node = node.children[ch]

return node.is_word

def startsWith(self, prefix: str) -> bool:
"""
Returns if there is any word in the trie that starts with the given prefix.
"""
node = self.root

for ch in prefix:
if ch not in node.children:
return False
else:
node = node.children[ch]

return True

# Your Trie object will be instantiated and called as such:
# obj = Trie()
# obj.insert(word)
# param_2 = obj.search(word)
# param_3 = obj.startsWith(prefix)``````
• Time Complexity: ~M, where M is the key length.
• Space Complexity: ~1