实现一个字典树
class Trie(object):
def __init__(self):
self.root = TrieNode()
def insert(self, word):
cur = self.root
for i in word:
cur = cur.children[i]
cur.is_word = True
def search(self, word):
cur = self.root
for i in word:
cur = cur.children.get(i)
if cur is None:
return False
return cur.is_word
def startsWith(self, prefix):
cur = self.root
for i in prefix:
cur = cur.children.get(i)
if cur is None:
return False
return True
class TrieNode(object):
def __init__(self):
self.children = collections.defaultdict(TrieNode)
self.is_word = False