-
Notifications
You must be signed in to change notification settings - Fork 0
/
trie.py
34 lines (27 loc) · 804 Bytes
/
trie.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
from collections import defaultdict
class TrieNode:
def __init__(self):
self.word = False
self.children = defaultdict(TrieNode)
class Trie:
def __init__(self) -> None:
self.root = TrieNode()
def insert(self, word):
node = self.root
for char in word:
node = node.children[char]
node.word = True
def search(self, word):
node = self.root
for char in word:
if char not in node.children:
return False
node = node.children[char]
return node.word
def startswith(self, prefix):
node = self.root
for char in prefix:
if char not in node.children:
return False
node = node.children[char]
return True