在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
热门推荐
1 训练狗狗基础
2 怎么训练狗狗笑
3 怎么训练狗狗卧下
4 上海狗狗训练基地
5 训练狗狗排便
6 狗狗基础训练
8 如何训练狗狗装死
9 狗狗站姿训练
10 狗狗训练用品
11 训练狗狗吧
12 狗狗要怎么训练
13 怎么训练狗狗玩球
14 训练狗狗唤回
15 狗狗训练躺下
16 狗狗训练指令
17 狗狗的训练技巧
18 狗狗不好训练