在Python中实现Trie（前缀树）
假设我们必须创建trie结构，使用三种基本操作，如insert()、search()、startsWith()方法。我们可以假设所有输入都是小写字母。例如，如果我们按如下方式调用函数，我们将看到输出
Trietrie=newTrie()
trie.insert("apple")
trie.search("apple") //returntrue
trie.search("app") //returnfalse
trie.startsWith("app") //returntrue
trie.insert("app")
trie.search("app") //returntrue
为了解决这个问题，我们将遵循以下步骤-
让我们看下面的实现以更好地理解-
示例
class Trie(object):
def __init__(self):
self.child = {}
def insert(self, word):
current = self.child
for l in word:
if l not in current:
current[l] = {}
current = current[l]
current['#']=1
def search(self, word):
current = self.child
for l in word:
if l not in current:
return False
current = current[l]
return '#' in current
def startsWith(self, prefix):
current = self.child
for l in prefix:
if l not in current:
return False
current = current[l]
return True
ob1 = Trie()ob1.insert("apple")
print(ob1.search("apple"))
print(ob1.search("app"))
print(ob1.startsWith("app"))
ob1.insert("app")
print(ob1.search("app"))输入值
ob1 = Trie()ob1.insert("apple")
print(ob1.search("apple"))
print(ob1.search("app"))
print(ob1.startsWith("app"))
ob1.insert("app")
print(ob1.search("app"))输出结果
True False True True