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
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
|
""" Tries in python
Methods - insert_key(k, v)
has_key(k)
retrie_val(k)
start_with_prefix(prefix)
"""
def _get_child_branches(trie):
"""
Helper method for getting branches
"""
return trie[1:]
def _get_child_branch(trie, c):
"""
Get branch matching the character
"""
for branch in _get_child_branches(trie):
if branch[0] == c:
return branch
return None
def _retrive_branch(k, trie):
"""
Get branch matching the key word
"""
if not k:
return None
for c in k:
child_branch = _get_child_branch(trie, c)
if not child_branch:
return None
trie = child_branch
return trie
def _is_trie_bucket(bucket):
if len(bucket) != 2:
return False
return type(bucket[1]) is tuple
def _get_bucket_key(bucket):
if not _is_trie_bucket(bucket):
return None
return bucket[1][0]
def has_key(k, trie):
"""
Check if trie contain the key word
"""
return _retrive_branch(k, trie) is not None
def retrie_val(k, trie):
key_tuple = _retrive_branch(k, trie)
if not key_tuple:
return None
return key_tuple[1]
def insert_key(key, v, trie):
"""
Insert a (key, value) pair into trie
"""
if not key or has_key(key, trie):
return
for char in key:
branch = _get_child_branch(trie, char)
if not branch:
new_branch = [char]
trie.append(new_branch)
trie = new_branch
else:
trie = branch
trie.append((key, v))
def start_with_prefix(prefix, trie):
"""
Find words start with prefix
"""
branch = _retrive_branch(prefix, trie)
if not branch:
return []
prefix_list = []
q = branch[1:]
while q:
curr_branch = q.pop(0)
if _is_trie_bucket(curr_branch):
prefix_list.append(_get_bucket_key(curr_branch))
else:
q.extend(curr_branch[1:])
return prefix_list
|
