Python裏面用什麽trie樹實現模塊比較好

鏈接：/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