PythonでオートコンプリートをサポートするTrieを実装する

Question

私はウェブサイトでオートコンプリートをサポートするデータ構造を実装しようとしています。 私はTrieの反復バージョンを実装することができました。これは、Trieでの追加と検索という2つの主要な方法をサポートしています。 しかし、次の接頭辞で始まるすべての単語を返すメソッドを追加する必要があります。誰かがこれで私を助けることができますか？

class Trie: 
    def __init__(self): 
     self.root = TrieNode() 

    def insert(self, word): 
     curr = self.root 
     for letter in word: 
      node = curr.children.get(letter) 
      if not node: 
       node = TrieNode() 
       curr.children[letter] = node 
      curr = node 
     curr.end = True 

    def search(self, word): 
     curr = self.root 
     for letter in word: 
      node = curr.children.get(letter) 
      if not node: 
       return False 
      curr = node 
     return curr.end 

    def all_words_beginning_with_prefix(self, prefix): 
     #I'm not sure how to go about this one. 

Answer 1

他のメソッドと同じ方法でプレフィックスに従ってTrieを反復するジェネレータを実装するだけで済みます。

class TrieNode: 
    def __init__(self): 
     self.end = False 
     self.children = {} 

    def all_words(self, prefix): 
     if self.end: 
      yield prefix 

     for letter, child in self.children.items(): 
      yield from child.all_words(prefix + letter) 

class Trie: 
    # existing methods here 
    def all_words_beginning_with_prefix(self, prefix): 
     cur = self.root 
     for c in prefix: 
      cur = cur.children.get(c) 
      if cur is None: 
       return # No words with given prefix 

     yield from cur.all_words(prefix) 

trie = Trie() 
trie.insert('foobar') 
trie.insert('foo') 
trie.insert('bar') 
trie.insert('foob') 
trie.insert('foof') 

print(list(trie.all_words_beginning_with_prefix('foo'))) 

出力を：あなたは接頭辞の最後にノードを見つけたら、端末ノードが発見されたときには、接頭辞を追跡し、それを得ながら、サブトライを反復するためにyield fromと再帰的なジェネレータを使用することができます。

['foo', 'foob', 'foobar', 'foof']