title: How to make depth search in Trie?
body: <p>I wrote my <strong>Trie</strong> solution, where I used <strong>defaultdict</strong>. The task is to find all words with prefix.
  The format must be like {of:[of, offten, offensive]}</p>
  
  <p>Here my Trie class:</p>
  
  <pre><code>from collections import defaultdict
  
  def _trie():
      return defaultdict(_trie)
  
  TERMINAL = None
  
  class Trie(object):
      def __init__(self):
          self.trie = _trie()
  
      def addWord(self, word):
          trie = self.trie
          for letter in word:
              trie = trie[letter]
          trie[TERMINAL]
  
  
      def search(self, word, trie=None):
          if trie is None:
              trie = self.trie
          for i, letter in enumerate(word):
              if letter in trie:
                  trie = trie[letter]
              else:
                  return False
          return trie
  </code></pre>
  
  <p>Here The example:</p>
  
  <pre><code>Trie = Trie()
  Trie.addWord('of')
  Trie.addWord('often')
  Trie.addWord('offensive')
  
  
  string = 'of'
  s = dict(Trie.search(string))
  </code></pre>
  
  <p>They give the result:<a href="https://i.stack.imgur.com/pwU1z.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/pwU1z.png" alt="enter image description here"></a></p>