数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究用 Python 实现 Trie（前缀树）
假设我们需要构建一个 Trie 结构，并实现三个基本操作：插入 (insert())、搜索 (search()) 和以某个前缀开头 (startsWith()) 方法。我们可以假设所有输入都是小写字母。例如，如果我们按如下方式调用这些函数，我们将看到相应的输出
- Trie trie = new Trie()
- trie.insert(“apple”)
- trie.search(“apple”) //这将返回 true
- trie.search(“app”) //这将返回 false
- trie.startsWith(“app”) //这将返回 true
- trie.insert(“app”)
- trie.search(“app”) //这将返回 true
为了解决这个问题，我们将遵循以下步骤：
- 最初创建一个名为 child 的字典。
- insert 方法将如下所示：
- current := child
- 对于单词中的每个字母 l：
- 如果 l 不存在于 current 中，则 current[l] := 新字典
- current := current[l]
- current[#] = 1
- search 方法将如下所示：
- current := child
- 对于单词中的每个字母 l：
- 如果 l 不存在于 current 中，则返回 false
- current := current[l]
- 如果 current[#] = 1，则返回 true，否则返回 false
- startsWith 方法将如下所示：
- current := child
- 对于单词中的每个字母 l：
- 如果 l 不存在于 current 中，则返回 false
- current := current[l]
- 返回 True
让我们看看下面的实现来更好地理解：
示例
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
更新于: 2020年5月4日
5K+ 浏览量
广告