实现

  1. class Trie:
  2.     def __init__(self):
  3.         self.root = {"is_word": False}
  4.         self.size = 0
  6.     # 返回单词数量
  7.     def get_size(self):
  8.         return self.size
  10.     # 向trie中添加一个单词
  11.     def add(self, words):
  12.         cur = self.root
  13.         for i in words:
  14.             if i not in cur:
  15.                 cur[i] = dict(is_word=False)
  16.                 self.size += 1
  17.             cur = cur[i]
  19.         if not cur["is_word"]:
  20.             cur["is_word"] = True
  22.     # 是否包含某个单词
  23.     def contains(self, words):
  24.         cur = self.root
  25.         for i in words:
  26.             if i not in cur:
  27.                 return False
  28.             cur = cur[i]
  29.         return cur["is_word"]
  31.     # 查询是否存在单词已words_prefix作为前缀
  32.     def is_prefix(self, words_prefix):
  33.         cur = self.root
  34.         for i in words_prefix:
  35.             if i not in cur:
  36.                 return False
  37.             cur = cur[i]
  38.         return True