Return to Revisions

find is not correct. If the final character occurs elsewhere in the string, the method returns True at that point. You can fix this and simplify the code at the same time:

  @staticmethod
  def find(trie, word):
      for char in word:
          if char in trie.child:
              trie = trie.child[char]
          else:
              return False
      return True

The point of static methods is that they can be called without an instance of the class. Your static methods expect an instance as the first argument. Thus they could be normal instance methods instead.

Here the first assignment is redundant. If dict lookup raises KeyError, that will occur before the assignment anyway, so the value of node is preserved even if you only use node = node.child[s[i]].

      try:
          _ = node.child[s[i]]
          node = node.child[s[i]]
          i = i + 1
      except KeyError:
          break

The while loops can be changed to for loops like this for example:

  def insert(self, s, value = 0):
      node = self
      for i, char in enumerate(s):
          try:
              node = node.child[char]
          except KeyError:
              break
      else:
          i += 1

      # (* append new nodes, if necessary *)
      for char in s[i:]:
          node.child[char] = node = Trie()

      node.value = value

(Note that in a chained assignment like node.child[char] = node = Trie() the right-hand-side is evaluated first and then assigned to the targets from left to right)

You could also take advantage of collections.defaultdict and greatly simplify insert:

  def __init__(self):
      self.child = collections.defaultdict(Trie)

  def insert(self, s, value = 0):
      node = self
      for char in s:
          node = node.child[char]
      node.value = value