Repository navigation
Expand file tree
/
Copy pathtrie_with_array.py
More file actions
71 lines (58 loc) · 2.53 KB
/
Copy pathtrie_with_array.py
File metadata and controls
71 lines (58 loc) · 2.53 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
63
64
65
66
67
68
69
70
71
class TrieWithArray[T]:
r"""Trie (Array-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 fixed-size array of 26 slots (one per lowercase
letter a-z), indexed by `ord(char) - ord("a")`. Lookups are O(1) per character since the child slot is
computed directly, but every node reserves space for all 26 possible children whether or not they are
used.
"""
def __init__(self):
self.head: TrieNode[T] = TrieNode[T]()
def insert(self, word: str) -> None:
"""Inserts a word into the trie."""
current_trie = self.head
for index in range(1, len(word) + 1):
node_index = ord(word[:index][-1]) - ord("a")
next_node = current_trie.child_nodes[node_index]
if next_node is not None:
current_trie = next_node
else:
new_node = TrieNode()
current_trie.child_nodes[node_index] = new_node
current_trie = new_node
def search(self, word: str) -> bool:
"""Returns True if the word is in the trie."""
current_trie = self.head
for index in range(1, len(word) + 1):
node_index = ord(word[:index][-1]) - ord("a")
next_node = current_trie.child_nodes[node_index]
if next_node is not None:
current_trie = next_node
else:
return False
return current_trie.child_nodes == [None] * 26
def starts_with(self, prefix: str) -> bool:
"""Returns True 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):
node_index = ord(prefix[:index][-1]) - ord("a")
next_node = current_trie.child_nodes[node_index]
if next_node is not None:
current_trie = next_node
else:
return False
return True
class TrieNode[T]:
def __init__(self):
self.child_nodes: list[TrieNode[T] | None] = [None] * 26