在 Python 中实现 Trie(前缀树)

pythonserver side programmingprogramming更新于 2025/11/22 21:32:17

假设我们必须创建 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 的字典。
插入方法将类似于 −
current := child
对于单词中的每个字母 l −
- 如果 l 不在 current 中，则 current[l] := new dictionary
- current := current[l]
current[#] = 1
搜索方法将类似于 −
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"))