LintCode Q442 Implement Trie in Python

  • Jinhai ZHOU
  • 7 Minutes
  • 2016年11月5日
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
"""
Your Trie object will be instantiated and called as such:
trie = Trie()
trie.insert("lintcode")
trie.search("lint") will return false
trie.startsWith("lint") will return true
"""
class TrieNode:
def __init__(self):
# Initialize your data structure here.
# No need to set a variable to save current character
self.childs = [None]*26 # inpus are consist of only a to z
self.end = False
class Trie:
def __init__(self):
self.root = TrieNode()
# @param {string} word
# @return {void}
# Inserts a word into the trie.
def insert(self, word):
current = self.root
for char in word:
index = ord(char) - ord('a')
if current.childs[index] is None:
new = TrieNode()
current.childs[index] = new
current = current.childs[index]
current.end = True
# @param {string} word
# @return {boolean}
# Returns if the word is in the trie.
def search(self, word):
current = self.root
for char in word:
index = ord(char) - ord('a')
if current.childs[index] is None:
return False
else:
current = current.childs[index]
return current.end
# @param {string} prefix
# @return {boolean}
# Returns if there is any word in the trie
# that starts with the given prefix.
def startsWith(self, prefix):
current = self.root
for char in prefix:
index = ord(char) - ord('a')
if current.childs[index] is None:
return False
else:
current = current.childs[index]
return True
知识共享许可协议
本作品采用知识共享署名-相同方式共享 4.0 国际许可协议进行许可。