鏈接:/question/21610353/answer/93639666
來源:知乎
著作權歸作者所有。商業轉載請聯系作者獲得授權,非商業轉載請註明出處。
Trie樹是壹種樹的數據結構,又被稱為字典樹,非常適用於Ajax自動補全等場景,因為它通過空間換時間能極大提高特別字符串的查詢速度。
class TrieTree(object):
def __init__(self):
self.tree = {}
def add(self, word):
tree = self.tree
for char in word:
if char in tree:
tree = tree[char]
else:
tree[char] = {}
tree = tree[char]
tree['exist'] = True
def search(self, word):
tree = self.tree
for char in word:
if char in tree:
tree = tree[char]
else:
return False
if "exist" in tree and tree["exist"] == True:
return True
else:
return False
tree = TrieTree()
tree.add("abc")
tree.add("bcd")
print(tree.tree)
# Print {'a': {'b': {'c': {'exist': True}}}, 'b': {'c': {'d': {'exist': True}}}}
print(tree.search("ab"))
# Print False
print(tree.search("abc"))
# Print True
print(tree.search("abcd"))
# Print False