Posted on 2023-03-17 16:18
Uriel 阅读(19)
评论(0) 编辑 收藏 引用 所属分类:
数据结构 、
闲来无事重切Leet Code
实现Trie树的三种操作：插入、查找是否包含某个单词，以及是否包含某个前缀
1 #208
2 #Runtime: 184 ms (Beats 54.16%)
3 #Memory: 40.8 MB (Beats 42.22%)
4
5 class Node:
6 def __init__(self):
7 self.sons = {}
8 self.eow = False
9
10
11 class Trie(object):
12
13 def __init__(self):
14 self.root = Node()
15
16
17 def insert(self, word):
18 """
19 :type word: str
20 :rtype: None
21 """
22 r = self.root
23 for ch in word:
24 if ch not in r.sons:
25 r.sons[ch] = Node()
26 r = r.sons[ch]
27 r.eow = True
28
29
30 def search(self, word):
31 """
32 :type word: str
33 :rtype: bool
34 """
35 r = self.root
36 for ch in word:
37 if ch not in r.sons:
38 return False
39 r = r.sons[ch]
40 return r.eow
41
42
43 def startsWith(self, prefix):
44 """
45 :type prefix: str
46 :rtype: bool
47 """
48 r = self.root
49 for ch in prefix:
50 if ch not in r.sons:
51 return False
52 r = r.sons[ch]
53 return True
54
55
56
57 # Your Trie object will be instantiated and called as such:
58 # obj = Trie()
59 # obj.insert(word)
60 # param_2 = obj.search(word)
61 # param_3 = obj.startsWith(prefix)