在Python中实现Trie（前缀树）

假设我们必须创建trie结构，使用三种基本操作，如insert()、search()、startsWith()方法。我们可以假设所有输入都是小写字母。例如，如果我们按如下方式调用函数，我们将看到输出

• Trie trie = new Trie()

• trie.insert("apple")

• trie.search("apple")     // return true

• trie.search("app")        //return false

• trie.startsWith("app")   //return true

• trie.insert("app")

• trie.search("app")        // return 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