python实现前缀树（Trie）

所有输入均为小写字母

class TrieNode:
  def __init__(self):
      self.child = [None for _ in range(26)]
      self.isEnd = False
  def contain_key(self, c):
      return self.child[ord(c)-ord('a')]!=None
  def get(self, c):
      return self.child[ord(c)-ord('a')]
  def put(self, c):
      self.child[ord(c)-ord('a')] = TrieNode()
class Trie:

  def __init__(self):
      """
      Initialize your data structure here.
      """
      self.root = TrieNode()

  def insert(self, word: str) -> None:
      """
      Inserts a word into the trie.
      """
      t = self.root
      for w in word:
          if not t.contain_key(w):
              t.put(w)
          t = t.get(w)
      t.isEnd = True

  def search(self, word: str) -> bool:
      """
      Returns if the word is in the trie.
      """
      t = self.root
      for w in word:
          if not t.contain_key(w):
              return False
          t = t.get(w)
      return t.isEnd

  def startsWith(self, prefix: str) -> bool:
      """
      Returns if there is any word in the trie that starts with the given prefix.
      """
      t = self.root
      for w in prefix:
          if not t.contain_key(w):
              return False
          t = t.get(w)
      return True