PythonでTrie（プレフィックスツリー）を実装する

insert（）、search（）、startsWith（）メソッドのような3つの基本的な操作でtrie構造を作成する必要があるとします。すべての入力は小文字であると想定できます。たとえば、次のように関数を呼び出すと、出力が表示されます

• 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を返します

これを解決するには、次の手順に従います-

• 最初に、子と呼ばれる1つの辞書を作成します。
• 挿入方法は次のようになります-
• 現在：=子
• 単語の各文字lについて-
  • lがcurrentに存在しない場合、current [l]：=新しい辞書
  • current：=current [l]
• current [＃] =1
• 検索方法は次のようになります-
• 現在：=子
• 単語の各文字lについて-
  • lがcurrentに存在しない場合は、falseを返します
  • current：=current [l]
• current [＃] =1の場合はtrueを返し、それ以外の場合はfalseを返します
• startsWithメソッドは次のようになります-
• 現在：=子
• 単語の各文字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