Trie
01 / The one-sentence essence
Store a set of strings on a tree of characters — each node is a prefix, each edge is a character, and a special end-of-word marker distinguishes "this prefix is also a stored word" from "this is just a prefix on the way to longer words."
Problemstore + search words on a prefix treeOps7Split4 insert · 3 search
Empty trie — just the root. Each operation walks the tree one character at a time.
step
0 / 35
op
—
nodes
1
last result
—
0 / 35
02 / The pattern signature
# a trie node is a map + an "is this a word ending" flagclass Node:children: dict[char, Node] = {}is_end: bool = False def insert(word):node = rootfor ch in word:if ch not in node.children:node.children[ch] = Node()node = node.children[ch]node.is_end = True def search(word):node = walk(word) # follow each char or return None on missreturn node is not None and node.is_end
03 / When to recognize this pattern
"prefix queries"
The problem cares about prefixes, not just full matches — autocomplete, longest-common-prefix, "all words starting with X". A hash set can't answer these in better than linear scan.
"dictionary of words"
A fixed dictionary you'll query many times. The dictionary is the trie; queries are walks. Build cost is amortized over every query.
"alphabet-bounded keys"
Each step branches on one of a small fixed set of values — lowercase letters (26), digits (10), IP octets (256). When the alphabet is unbounded or continuous, a different structure fits better.
"shared structure"
Words like
"car", "card", "care", "cart" share the same first three nodes — the trie stores that prefix once. If most words don't share prefixes, the trie is a thin wrapper around a hash set and the win shrinks.04 / Common pitfalls
i.
Forgetting the end-of-word marker.
Reaching the last character of a search word isn't enough — you also need the node to be marked as
is_end. If you skip the marker, search("ca") will succeed after inserting "cat", which is wrong. The marker is what turns a prefix tree into a word set.ii.
Confusing search with startsWith.
search(w) requires the terminal node to be marked. startsWith(p) only requires that the walk completes — no end-of-word check. The same walking code underlies both; the post-condition differs by one line.iii.
Using a 26-slot array when keys aren't bounded.
A fixed
children[26] array is fast and cache-friendly for lowercase-only alphabets but becomes a memory disaster on larger alphabets (Unicode, byte streams). Default to a hash map; switch to a fixed array only when the alphabet is small and the inner loop is hot.05 / Go practice — on LeetCode
Four problems across the family. The first is the canonical "build the data structure" exercise. The next two add features (wildcards, multi-board search). The fourth flips the query: given a dictionary, find the longest word with a specific structural property.