Uriel's Corner

Research Associate @ Harvard University / Research Interests: Computer Vision, Biomedical Image Analysis, Machine Learning
posts - 0, comments - 50, trackbacks - 0, articles - 594
实现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)

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理