Implement a basic trie (prefix tree) with insert, search, and startsWith methods
Gordon Ramsey of Code
Performer
```python
class Trie:
def __init__(self):
self.root = {}
def insert(self, word: str) -> None:
node = self.root
for char in word:
if char not in node:
node[char] = {}
node = node[char]
node['#'] = True
def search(self, word: str) -> bool:
node = self.root
for char in word:
if char not in node:
return False
node = node[char]
return '#' in node
def startsWith(self, prefix: str) -> bool:
node = self.root
for char in prefix:
if char not in node:
return False
node = node[char]
return True
```
```python
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:
node = self.root
for char in word:
if char not in node.children:
node.children[char] = TrieNode()
node = node.children[char]
node.is_word = True
def search(self, word: str) -> bool:
node = self.root
for char in word:
if char not in node.children:
return False
node = node.children[char]
return node.is_word
def startsWith(self, prefix: str) -> bool:
node = self.root
for char in prefix:
if char not in node.children:
return False
node = node.children[char]
return True
```Old School Unix Wizard
Roaster
“A dictionary of dictionaries? What is this, a data structure for toddlers? Back in my day, we used arrays and bit shifts, and we LIKED it. I bet you've never even seen `malloc`, have you? And what's with the `#` at the end? Are you marking your territory? ”
“"Python? A dictionary of dictionaries? Son, Ken and Dennis are spinning in their graves. You call that a trie? It's an abomination! I bet you're allocating memory faster than the PDP-7 can keep up." ”
“"Python? A hash table for a tree? Dennis Ritchie is rolling in his grave. Using a '#' as a sentinel? Son, `\0` has been doing that job just fine since Bell Labs. Go back to your scripting kiddie language and learn some real data structures." ”
“WHAT IS THIS, A CHILDREN'S MENU? You call this an `insert` function? It's BLOODY RAW! You're just iterating, creating nodes, and moving on. WHERE'S THE `is_word` MARK, YOU DONKEY? The dish is incomplete! ”
“ARE YOU HAVING A LAUGH? This `startsWith` method is BLOODY AWFUL. You're traversing the trie, but you're not even checking `is_word` at the end, you DONKEY! It's like serving a raw chicken and calling it dinner. ”
“ARE YOU KIDDING ME, YOU DONKEY?! This trie is so BASIC it's practically RAW! It's DRY, lifeless, and about as efficient as a BLIND man in a maze. ”