找到一种Trie 的实现：简单易懂，高效
trie适合使用的情况
查看string是否valid
查看string是否存在
class Trie(object):
def __init__(self):
"""
Initialize your data structure here.
Trie 的树用一颗个多层dic来代表
"""
self.tr = {}
def insert(self, word):
"""
Inserts a word into the trie.
:type word: str
:rtype: void
插入单个单词，对每个字母进行插入，
setdefault(Key,Val),会完成插入dict.insert(val)，
并且返回 val，这是返回一个空辞典,具体使用：
>>> a.setdefault("1",1)
1
>>> a.setdefault("1",2)
1
>>> a
{'1': 1}
"""
temp = self.tr
for char in word:
temp = temp.setdefault(char,{})
temp["end"] = ""
# print self.tr
def search(self, word):
"""
Returns if the word is in the trie.
:type word: str
:rtype: bool
不停的进入dict内部的dict进行搜索
"""
temp = self.tr
for char in word:
if char in temp:
temp = temp[char]
continue
return False
return "end" in temp
def startsWith(self, prefix):
"""
Returns if there is any word in the trie that starts with the given
prefix.
:type prefix: str
:rtype: bool
与 search同理
"""
temp = self.tr
for char in prefix:
if char in temp:
temp = temp[char]
continue
return False
return True
