Friedrich Ewald My Personal Website

Leetcode: Trie Prefix Tree

Create an implementation of a Trie structure. 

class Node:
  def __init__(self, val: str, children: dict[str, 'Node'] = {}) -> None:
    print('init node', val)
    self.val = val
    self.children = children
    self.is_word = False


class Trie:
    def __init__(self):
        self.root = Node('', {})
        print(self.root.children)

    def insert(self, word: str) -> None:
        print('inserting', word)
        root = self.root
        while word != '':
            char = word[0]
            word = word[1:]

            if char not in root.children:
                root.children[char] = Node(char, {})
            root = root.children[char]
        root.is_word = True

    def search(self, word: str) -> bool:
        root = self.root
        while word != '':
            char = word[0]
            word = word[1:]
            if char not in root.children:
                return False
            root = root.children[char]
        return root.is_word

    def startsWith(self, prefix: str) -> bool:
        root = self.root
        while prefix != '':
            char = prefix[0]
            prefix = prefix[1:]
            print(char, root.children)
            if char not in root.children:
                return False
            root = root.children[char]
        return True
The same tree, but with allowing placeholders in the form of . can be implemented as follows: 
class Node:
  def __init__(self, val: str, children: dict[str, 'Node']):
    self.val = val
    self.children = children
    self.is_word = False


class WordDictionary:
  def __init__(self):
    self.root = Node('', {})        

  def addWord(self, word: str) -> None:
    root = self.root
    while word != '':
      char = word[0]
      word = word[1:]
      if char not in root.children:
        root.children[char] = Node(char, {})
      root = root.children[char]
    root.is_word = True

  def search(self, word: str) -> bool:
    root = self.root
    return self.inner(root, word)

  def inner(self, root: Node, word: str) -> bool:
    if root is None:
      return False

    if word == '':
      return root.is_word
    
    char = word[0]
    if char == '.':
      res = any([self.inner(child, word[1:]) for child in root.children.values()])
      return res
    else:
      if char in root.children:
        return self.inner(root.children[char], word[1:])
      else:
        return False

About the author

is a Staff Software Engineer with a Master's degree in Computer Science. He started this website in late 2015, mostly as a digital business card. He is interested in Go, Python, Ruby, SQL- and NoSQL-databases, machine learning and AI and is experienced in building scalable, distributed systems and micro-services at multiple larger and smaller companies.

Related Posts