Repository navigation
Expand file tree
/
Copy pathtrie_with_dictionary.py
More file actions
62 lines (52 loc) · 2.33 KB
/
Copy pathtrie_with_dictionary.py
File metadata and controls
62 lines (52 loc) · 2.33 KB
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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
class TrieWithDictionary:
r"""Trie (Dictionary-backed).
A Trie is a special form of an N-ary tree. Typically, a trie is used to store strings. Each Trie node
represents a string (a prefix). Each node might have several children nodes while the paths to
different children nodes represent different characters. And the strings the child nodes represent
will be the origin string represented by the node itself plus the character on the path. - Leetcode
::
head
/ \\
a b
/ / \\
am bo be
/
bot
This implementation backs each node's children with a dictionary (hash table) keyed by the prefix
string represented so far, rather than a fixed-size array. This avoids reserving space for unused
characters and is not limited to a fixed alphabet, at the cost of hashing overhead per lookup.
"""
def __init__(self):
"""Initialize your data structure here."""
self.head: TrieNode = TrieNode()
def insert(self, word: str) -> None:
"""Inserts a word into the trie."""
current_trie = self.head
for index in range(1, len(word) + 1):
if word[:index] in current_trie.child_nodes:
current_trie = current_trie.child_nodes[word[:index]]
else:
child_node = TrieNode()
current_trie.child_nodes.setdefault(word[:index], child_node)
current_trie = child_node
def search(self, word: str) -> bool:
"""Returns if the word is in the trie."""
current_trie = self.head
for index in range(1, len(word) + 1):
if word[:index] in current_trie.child_nodes:
current_trie = current_trie.child_nodes[word[:index]]
else:
return False
return len(current_trie.child_nodes) == 0
def starts_with(self, prefix: str) -> bool:
"""Returns if there is any word in the trie that starts with the given prefix."""
current_trie = self.head
for index in range(1, len(prefix) + 1):
if prefix[:index] in current_trie.child_nodes:
current_trie = current_trie.child_nodes[prefix[:index]]
else:
return False
return True
class TrieNode:
def __init__(self):
self.child_nodes: dict[str, TrieNode] = {}