-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathtrie.py
More file actions
72 lines (63 loc) · 1.88 KB
/
trie.py
File metadata and controls
72 lines (63 loc) · 1.88 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
72
# 208. Implement Trie (Prefix Tree)
# https://leetcode.com/problems/implement-trie-prefix-tree
import unittest
class Trie:
def __init__(self):
"""
Initialize your data structure here.
"""
self.dic = {}
def insert(self, word):
"""
Inserts a word into the trie.
:type word: str
:rtype: void
"""
current_dic = self.dic
for char in word:
if char not in current_dic:
current_dic[char] = {}
current_dic = current_dic[char]
current_dic['*'] = True
def search(self, word):
"""
Returns if the word is in the trie.
:type word: str
:rtype: bool
"""
current_dic = self.dic
for char in word:
if char not in current_dic:
return False
current_dic = current_dic[char]
if '*' in current_dic:
return True
else:
return False
def startsWith(self, prefix):
"""
Returns if there is any word in the trie that starts with the given prefix.
:type prefix: str
:rtype: bool
"""
current_dic = self.dic
for char in prefix:
if char not in current_dic:
return False
current_dic = current_dic[char]
return True
class TestTrie(unittest.TestCase):
def test(self):
# Your Trie object will be instantiated and called as such:
obj = Trie()
obj.insert('apple')
self.assertFalse(obj.search('app'))
self.assertTrue(obj.startsWith('app'))
obj.insert('app')
self.assertTrue(obj.search('app'))
self.assertTrue(obj.startsWith('app'))
obj.insert('ap')
self.assertFalse(obj.search('aps'))
self.assertTrue(obj.startsWith('a'))
if __name__ == '__main__':
unittest.TestCase()