Trie Prefix Search Implementation

Coding · Medium · Free problem

Implement a Trie (prefix tree) data structure that supports the following operations, each running in $O(L)$ time where $L$ is the length of the input string:

  • insert(word) -- add a word to the trie
  • search(word) -- return True if the word exists in the trie (exact match), False otherwise
  • starts_with(prefix) -- return True if any word in the trie begins with the given prefix, False otherwise

Constraints: - Words consist of lowercase English letters only -

\le L \le 2000$ - All operations must complete in $O(L)$ time

Examples:

``` trie = Trie() trie.insert("apple") trie.search("apple") # True trie.search("app") # False (prefix exists but word not inserted) trie.starts_with("app") # True trie.insert("app") trie.search("app") # True ```

Hints

  1. Each trie node needs two things: a dictionary mapping characters to child nodes, and a boolean marking whether a complete word ends here.
  2. Both search and starts_with walk the trie the same way -- they differ only at the end: search requires is_end == True, starts_with just requires the path to exist.
  3. Factor out the common prefix-walking logic into a helper _find_node(s) that returns the terminal node (or None if the path is missing), then implement search and starts_with in terms of it.

Worked Solution

How to Think About It: A trie is a tree where each path from root to a marked node spells out a word. Each node stores a dictionary of children (one per character) and a boolean flag marking end-of-word. Insert and search both walk the trie one character at a time -- $O(L)$ per operation. The key difference between search and starts_with is just whether you check the end-of-word flag at the final node.

Algorithm:

  • insert: Walk the trie character by character, creating nodes as needed. Mark the final node as end-of-word.
  • search: Walk the trie character by character. If any character is missing, return False. If the walk completes, check the end-of-word flag.
  • starts_with: Same as search, but do NOT check the end-of-word flag -- you only care that the path exists.

Code:

```python class TrieNode: def __init__(self): self.children = {} # char -> TrieNode self.is_end = False

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

def insert(self, word: str) -> None: node = self.root for ch in word: if ch not in node.children: node.children[ch] = TrieNode() node = node.children[ch] node.is_end = True

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

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

def _find_node(self, s: str): """Walk the trie along string s. Return the final node, or None if path missing.""" node = self.root for ch in s: if ch not in node.children: return None node = node.children[ch] return node ```

Why this is correct: - insert creates the path if it does not exist and marks the terminal node. Subsequent inserts of the same word are idempotent. - search returns True only when the full path exists AND the final node is marked as a word endpoint. This correctly distinguishes "app" (inserted) from "app" as a prefix of "apple" (not marked). - starts_with returns True whenever the prefix path exists, regardless of whether any node along it is marked end-of-word.

Complexity: - Time: $O(L)$ per operation -- one dictionary lookup per character. - Space: $O(\sum L_i)$ in the worst case -- if no words share prefixes, every character is a new node. In practice, shared prefixes are stored once, which is the space advantage of a trie over a hash set.

Answer: Trie with TrieNode.children (dict) and TrieNode.is_end (bool). All three operations run in $O(L)$ time. The only difference between search and starts_with is checking is_end at the terminal node.

Intuition

The trie's key property is that it trades space for time in a specific way: shared prefixes are stored once, so lookups are $O(L)$ regardless of how many words are in the dictionary -- unlike a hash set where collisions can degrade performance, or a sorted list where search is $O(L \log n)$. This makes tries the right data structure whenever you are doing repeated prefix lookups over a large dictionary of strings.

In quant and systems contexts, trie-like structures appear in: fast routing tables (IP prefix matching), autocomplete systems (find all completions of a prefix in $O(L + k)$ where $k$ is the number of results), and symbol table lookups in low-latency trading systems where you want guaranteed $O(L)$ access by ticker or instrument ID. The is_end flag is the subtle but critical detail -- it is what separates a prefix search (does any path exist?) from an exact match (does a complete word end here?). Missing that distinction is the most common implementation error.

Open the full interactive solver →