在python中可以用字典来实现字典树这一结构。
class Trie:
def __init__(self):
"""
Initialize your data structure here.
"""
self.root = {}
self.isEnd = '#'
def insert(self, word: str) -> None:
"""
Inserts a word into the trie.
"""
node = self.root
for char in word:
if char not in node:
node[char] = {} #如果没有这一字母则新建一个字典
node = node[char]
node[self.isEnd] = '#' #加上结束符
def search(self, word: str) -> bool:
"""
Returns if the word is in the trie.
"""
node = self.root
for char in word:
if char not in node:
return False
node = node[char]
return self.isEnd in node #如果没有# 说明只是前缀
def startsWith(self, prefix: str) -> bool:
"""
Returns if there is any word in the trie that starts with the given prefix.
"""
node = self.root
for char in prefix:
if char not in node:
return False
node = node[char]
return True
# Your Trie object will be instantiated and called as such:
# obj = Trie()
# obj.insert(word)
# param_2 = obj.search(word)
# param_3 = obj.startsWith(prefix)
2.采用defaultdict创建trie
from collections import defaultdict
from functools import reduce
TrieNode = lambda: defaultdict(TrieNode)
class Trie:
def __init__(self):
self.trie = TrieNode()
def insert(self, word):
reduce(dict.__getitem__, word, self.trie)['end'] = True
def search(self, word):
return reduce(lambda d,k: d[k] if k in d else TrieNode(), word, self.trie).get('end', False)
def startsWith(self, word):
return bool(reduce(lambda d,k: d[k] if k in d else TrieNode(), word, self.trie).keys())
collections,解释是数据类型容器模块。这里面有一个collections.defaultdict()经常被用到
这里的defaultdict(function_factory)构建的是一个类似dictionary的对象,其中keys的值,自行确定赋值,但是values的类型,是function_factory的类实例,而且具有默认值。比如default(int)则创建一个类似dictionary对象,里面任何的values都是int的实例,而且就算是一个不存在的key, d[key] 也有一个默认值,这个默认值是int()的默认值0.