# Problem Name
> [!META]- Inline Metadata
> [tags:: #career #concepts/programming/tries]
> [project group:: Neetcode 150]
> [difficulty:: done]
> [status:: in progress]
> [link:: https://leetcode.com/problems/implement-trie-prefix-tree/]
> [up:: [[Leetcode MOC]]]
## Problem
A [**trie**](https://en.wikipedia.org/wiki/Trie) (pronounced as "try") or **prefix tree** is a tree data structure used to efficiently store and retrieve keys in a dataset of strings. There are various applications of this data structure, such as autocomplete and spellchecker.
Implement the Trie class:
- `Trie()` Initializes the trie object.
- `void insert(String word)` Inserts the string `word` into the trie.
- `boolean search(String word)` Returns `true` if the string `word` is in the trie (i.e., was inserted before), and `false` otherwise.
- `boolean startsWith(String prefix)` Returns `true` if there is a previously inserted string `word` that has the prefix `prefix`, and `false` otherwise.
**Example 1:**
**Input**
```
["Trie", "insert", "search", "search", "startsWith", "insert", "search"]
[[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]
```
**Output**
```
[null, null, true, false, true, null, true]
```
**Explanation**
```
Trie trie = new Trie();
trie.insert("apple");
trie.search("apple"); // return True
trie.search("app"); // return False
trie.startsWith("app"); // return True
trie.insert("app");
trie.search("app"); // return True
```
**Constraints:**
- `1 <= word.length, prefix.length <= 2000`
- `word` and `prefix` consist only of lowercase English letters.
- At most `3 * 104` calls **in total** will be made to `insert`, `search`, and `startsWith`.
## Solution
### Mine
#### Python
```python
class TrieNode:
def __init__(self, value):
self.value = value
self.children = {}
self.end_of_word = False
class Trie:
def __init__(self):
self.root = TrieNode(None)
def insert(self, word: str) -> None:
current_node = self.root
for letter in word:
current_node = current_node.children.setdefault(letter, TrieNode(value=letter))
current_node.end_of_word = True
def search(self, word: str) -> bool:
current_node = self.root
for letter in word:
try:
current_node = current_node.children[letter]
except KeyError:
return False
if current_node.end_of_word:
return True
return False
def startsWith(self, prefix: str) -> bool:
current_node = self.root
for letter in prefix:
try:
current_node = current_node.children[letter]
except KeyError:
return False
return True
```
#### Rust
### LC's
## Things I Learned
## Scratchpad