Implement Trie

Support word insert, full-word search, and prefix search.

Start with the concrete trace below. It shows the state the algorithm must carry as it runs.

Problem trace

Implement Trie: Each root-to-node path is one shared prefix; terminal state distinguishes a complete word from a mere prefix.

Input and goalSupport word insert, full-word search, and prefix search.

Start with an empty rootThe root has no child before insert("app").

double border complete word

operationinsert("app")existingroot only

Recognize it

Many words share prefixes and queries distinguish prefix existence from complete-word membership.

Keep true

The root-to-node edge labels spell its prefix; terminal is true exactly for inserted complete words.

Reuse it

Store shared prefixes once and attach terminal or payload state to nodes.

Pattern: Tree of character maps.

Simple idea: Follow one child map per character. Add an end marker after the last character so a full word can be different from its prefix.

class Trie:
   def __init__(self) -> None:
      self.root: dict = {}

   def insert(self, word: str) -> None:
      node = self.root
      for char in word:
         node = node.setdefault(char, {})
      node[None] = True

   def _walk(self, text: str) -> dict | None:
      node = self.root
      for char in text:
         if char not in node:
            return None
         node = node[char]
      return node

   def search(self, word: str) -> bool:
      node = self._walk(word)
      return node is not None and None in node

   def starts_with(self, prefix: str) -> bool:
      return self._walk(prefix) is not None

Cost: $O(L)$ time for each operation and $O(totalcharacters)$ stored space.