Implement Trie (Prefix Tree) lintcode: http://www.lintcode.com/submission/3111458/
要点：这题trie的特殊点在字符不是表示在root里，而是在边上。而边是每个树结点上的map<char, child>来表示的。所以结点是placeholder，所以比字符数应该多1个。
- insertion:
- 如果用recursion来做，因为java和python是不支持pass-by-reference的，所以要在下一层call的外面判断是否结点不存在，并且如果不存在则创建结点。
- 字符串结束的marker是在叶结点上，所以是在i==len(word)这层的call里。这是insert的中止条件，直接返回
- 死记这条：insert的时候root是不会为null的
- search和startsWith:
- 结束条件有多个可能：1. root为空，说明对应的字符不存在，返回False，2. i==len(word): code里这个判断在1.之后，所以root是不为null的，然后判断root.isLeaf
- startsWith的code是类似的，除了不用判断isLeaf
class TrieNode(object):
def __init__(self):
"""
Initialize your data structure here.
"""
self.children = [None]*26
self.isLeaf = False
class Trie(object):
def __init__(self):
self.root = TrieNode()
def insert(self, word):
"""
Inserts a word into the trie.
:type word: str
:rtype: void
"""
def insertRec(word, i, root):
if i>=len(word):
if i == len(word):
root.isLeaf = True
return
c = ord(word[i])-ord('a')
if not root.children[c]:
root.children[c] = TrieNode()
insertRec(word, i+1, root.children[c])
insertRec(word, 0, self.root)
def search(self, word):
"""
Returns if the word is in the trie.
:type word: str
:rtype: bool
"""
def searchRec(word, i, root):
if not root:
return False
if i==len(word):
if root.isLeaf:
return True
else:
return False
c = ord(word[i])-ord('a')
return searchRec(word, i+1, root.children[c])
return searchRec(word, 0, self.root)
def startsWith(self, prefix):
"""
Returns if there is any word in the trie
that starts with the given prefix.
:type prefix: str
:rtype: bool
"""
def startsWithRec(prefix, i, root):
if not root:
return False
if i==len(prefix):
return True
c = ord(prefix[i])-ord('a')
return startsWithRec(prefix, i+1, root.children[c])
return startsWithRec(prefix, 0, self.root)
# Your Trie object will be instantiated and called as such:
# trie = Trie()
# trie.insert("somestring")
# trie.search("key")