Trie Patterns

A hash set answers “is this exact word present?” in $O(L)$. It cannot answer “is any word present that starts like this?” without scanning every key. A trie (prefix tree) stores words character by character along shared paths, so prefix questions cost only the length of the prefix — no matter how many words are stored.

The Tries page covers the data structure itself. This page is about recognising when a problem wants one, and the three shapes those problems take.

What you’ll learn

• The nested-dict trie — 6 lines, and why it beats a TrieNode class in an interview.
• Why an end-of-word marker is mandatory, not decorative.
• Wildcard search: how one . turns lookup into a DFS with branching.
• Trie-pruned search: the idea that makes LC 212 tractable, and the single most important thing a trie buys you.
• Three real LeetCode problems solved in the browser: 208, 648, 211.

The cue

You are looking at a trie when…

• The word “prefix” appears — 208, 648, 1268, 720.
• You must match many patterns against many strings at once. One string against one pattern is KMP; many against many is a trie.
• Search must support wildcards or partial matches — 211.
• You are doing a grid/DFS search for a whole dictionary of words, and need to abandon dead branches early — 212.
• Autocomplete, typeahead, or “suggest up to 3 products” — 1268.
• Bit-level prefixes: maximum XOR pair is a trie over bits — 421.

The anti-cue: if you only ever need exact whole-word lookup, use a set. A trie costs more memory and only pays for itself when prefixes matter.

The template — a trie in six lines

You do not need a class. A nested dictionary is faster to write, harder to get wrong, and just as fast in practice.

trie_nested_dict.py

def build_trie(words):
    root = {}
    for word in words:
        node = root
        for ch in word:
            node = node.setdefault(ch, {})   # descend, creating as needed
        node["$"] = True                     # end-of-word marker
    return root
 
 
trie = build_trie(["app", "apple"])
print(trie)
# {'a': {'p': {'p': {'$': True, 'l': {'e': {'$': True}}}}}}

setdefault(ch, {}) is the whole insert: it returns the existing child if there is one, otherwise creates and returns a new empty dict. Searching is the same walk:

trie_search.py

def walk(root, s):
    """Return the node reached by s, or None if the path breaks."""
    node = root
    for ch in s:
        if ch not in node:
            return None
        node = node[ch]
    return node
 
 
def search(root, word):                 # exact word present?
    node = walk(root, word)
    return node is not None and "$" in node
 
 
def starts_with(root, prefix):          # any word with this prefix?
    return walk(root, prefix) is not None

The end-of-word marker is not optional

Insert "apple" only, then ask for "app". Without a marker, the walk succeeds — a -> p -> p all exist — and you would wrongly report that "app" is a stored word. The marker is exactly what distinguishes “a word ends here” from “a word passes through here”, which is the entire difference between search and startsWith.

Use a key that cannot collide with a real character. "$" is conventional; None or a dedicated sentinel object also work. If the alphabet could contain $, pick something else.

Complexity, and what a trie actually buys

For n words of length up to L, over an alphabet of size |Σ|:

Operation	Trie	Hash set
Insert	$O(L)$	$O(L)$
Exact search	$O(L)$	$O(L)$ average
Prefix search	$O(L)$	$O(n \cdot L)$ — scan everything
All words with a prefix	$O(L + \text{matches})$	$O(n \cdot L)$
Space	$O(n \cdot L \cdot \|\Sigma\|)$ worst case	$O(n \cdot L)$

Exact lookup is not the reason to use a trie — a set matches it and uses less memory. The wins are the two prefix rows, and one more thing that does not fit in a table:

The real superpower: pruning a search

In LC 212 (Word Search II) you must find which of k dictionary words appear in a grid. Running a separate DFS per word is $O(k \cdot 4^{L})$ — hopeless.

With a trie, you run one DFS and carry a trie node alongside your grid position. The moment the current path’s characters leave the trie, no dictionary word can start that way, so you abandon the branch immediately. One traversal prunes against the entire dictionary at once. That is the idea worth taking from this page.

Visual intuition

Characters live on edges, and every shared prefix is stored exactly once — which is the property every problem in this family exploits.

triePrefix sharing, and why the end-of-word flag is separateprefix tree

1class TrieNode:2    def __init__(self):3        self.children = {}      # char -> TrieNode4        self.is_word = False    # NOT the same as 'has no children'5 6def insert(root, word):7    node = root8    for ch in word:9        if ch not in node.children:10            node.children[ch] = TrieNode()11        node = node.children[ch]12    node.is_word = True         # mark the END, not the node13 14def search(root, word):15    node = root16    for ch in word:17        if ch not in node.children: return False18        node = node.children[ch]19    return node.is_word         # prefix != word

setupA trie stores characters on **edges**, not in nodes, and shares every common prefix. That sharing is the whole point: "car" and "card" occupy one path, so prefix lookup costs O(length) regardless of how many words are stored.

Play‹›1/22⟲

Note that 'car' terminates inside the path to 'card'. Without an explicit end-of-word flag a trie cannot tell a stored word from a mere prefix, and 'is car a word' becomes unanswerable.

The variant map

Variant	What the trie does	Canonical problem
Basic prefix tree	Insert / search / startsWith	208 Implement Trie
Shortest matching prefix	Walk the word, stop at the first $	648 Replace Words
Wildcard search	On ., DFS into every child	211 Design Add and Search Words
Prune a grid DFS	Carry a trie node with the search position	212 Word Search II
Autocomplete / top-k	Walk to the prefix, then collect from the subtree	1268 Search Suggestions
Store a value at each word	Keep a payload beside the $ marker	677 Map Sum Pairs
Bitwise trie	Insert 32-bit numbers as paths; greedily take the opposite bit	421 Maximum XOR

Practice — real LeetCode problems

LC 208 — Implement Trie (Prefix Tree) · Medium

Problem. Implement a Trie class with three methods: insert(word), search(word) (is this exact word stored?), and startsWith(prefix) (is any stored word prefixed by this?).

Constraints. 1 <= len(word) <= 2000, lowercase English letters, up to 3 * 10^4 calls total.

Example. Insert "apple"; search("apple") is True, search("app") is False, startsWith("app") is True; then insert "app" and search("app") becomes True.

pch.exerciseTag pch.exerciseTitle

Editorial — approach, complexity, follow-ups

A trie is a tree whose edges are labelled with characters, so a path from the root spells a prefix. The nested dict represents it directly: each dict maps a character to its child dict.

Time $O(L)$ per operation. Space $O(\text{total characters inserted})$.

search("appl") returning False while startsWith("app") returns True is the pair that proves the marker is doing its job. search("") is False here because no empty word was inserted — had you called insert(""), the root itself would carry "$" and it would be True. Getting that right falls out of the design rather than needing a special case.

Follow-ups you should expect:

• “Use a class instead of dicts.” A TrieNode with children: dict and is_word: bool is more readable in production and the natural place to hang extra fields. In an interview, dicts are fewer lines and fewer bugs; say you know both and why you picked one.
• “Implement delete.” The interesting part: remove the marker, then prune upward while a node has no children and no marker. Recursion handles it cleanly. Worth practising — it is the follow-up that separates people who understand the structure from people who memorised insert.
• “Fixed 26-slot array instead of a dict?” Faster constant factor and predictable layout, but $26 \times$ the memory for sparse tries. Fine for lowercase-only; a dict generalises to any alphabet.
• “Count words with a given prefix?” Store a counter at each node, incremented on the way down during insert.

LC 648 — Replace Words · Medium

Problem. Given a dictionary of root words and a sentence, replace every word in the sentence with the shortest root in the dictionary that is a prefix of it. If no root matches, leave the word unchanged. Return the resulting sentence.

Constraints. 1 <= len(dictionary) <= 1000, 1 <= len(sentence) <= 10^6, lowercase letters and single spaces.

Examples. dictionary = ["cat","bat","rat"], sentence = "the cattle was rattled by the battery" gives "the cat was rat by the bat"

pch.exerciseTag pch.exerciseTitle

Editorial — approach, complexity, follow-ups

Build one trie from the roots, then walk each sentence word through it. Because a trie walk visits prefixes in increasing length order, the first end-of-word marker you meet is necessarily the shortest matching root — so you return immediately and never compare candidate lengths.

Time $O(\text{total dictionary characters} + \text{total sentence characters})$. Space $O(\text{dictionary characters})$.

The third test case is the one that matters: ["catt","cat",...] contains both "catt" and "cat", and the answer must use "cat". A solution that walks to the end of the word and keeps the last marker found, or that sorts the dictionary by length and checks prefixes with startswith, gets this wrong or does far more work.

The brute-force alternative — for each word, test every root with word.startswith(root) — is $O(\text{words} \times \text{roots} \times L)$. With 1000 roots and a $10^6$-character sentence that is too slow, which is exactly why the trie is wanted.

Follow-ups you should expect: “Longest matching root instead?” — keep walking and remember the last marker seen. “What if roots can be added dynamically?” — inserting into the trie is $O(L)$, so nothing changes. “Preserve multiple spaces / punctuation?” — split() collapses whitespace, so switch to a manual scan or re.split and say so.

LC 211 — Design Add and Search Words Data Structure · Medium

Problem. Implement WordDictionary with addWord(word) and search(word), where the searched word may contain . as a wildcard matching any single character.

Constraints. 1 <= len(word) <= 25, lowercase letters for addWord; search words may contain up to 2 dots (and up to 3 in the harder tests). At most 10^4 calls.

Example. Add "bad", "dad", "mad". Then search("pad") is False, search("bad") is True, search(".ad") is True, search("b..") is True.

pch.exerciseTag pch.exerciseTitle

Editorial — approach, complexity, follow-ups

addWord is the standard insert. search can no longer be a simple loop, because a . has no single child to descend into — it must try all of them. That makes it a DFS with backtracking over (node, index) pairs.

Time for addWord: $O(L)$. For search: $O(L)$ when there are no wildcards; worst case $O(|\Sigma|^{d} \cdot L)$ where d is the number of dots, since each dot multiplies the branching. With d <= 3 and |Σ| = 26 that is bounded and fine. Space $O(L)$ for the recursion.

Skip the "$" key when branching on a wildcard

node.items() includes the end-of-word marker, whose value is True, not a child dict. Recursing into it raises TypeError (or silently misbehaves if your marker is a dict). The if key != "$" guard is mandatory.

This is the strongest argument for a TrieNode class in this particular problem: with children as its own dict, the marker simply is not in the iteration and the bug cannot happen. If you prefer dicts, know this trap.

The length check matters too. search("b.") is False because every stored word has length 3 — reaching the end of the search string must coincide with a stored word ending, which is what i == len(word) plus the marker test enforces. Likewise search("....") is False: four wildcards cannot match a three-letter word. A solution that returns True as soon as it runs out of pattern gets both wrong.

Follow-ups you should expect: “Support * (zero or more characters)?” — much harder; the DFS must also try consuming nothing and staying at the same node, and you need memoisation on (node_id, index) to avoid blow-up. “Many dots?” — group stored words by length first, so a search only explores words of the matching length. “Delete a word?” — clear the marker and prune childless nodes upward.

LeetCode problem set

Generated from the problem database, so each entry carries its sheet membership and reported companies. Tick them off as you go — progress is saved in this browser, and the Export button writes it to a file you can keep.

LC 421 is the one nobody expects to be a trie

“Find the maximum XOR of any two numbers in an array” looks like bit manipulation, and it is — but the efficient solution is a trie over the binary representations. Insert every number as a 32-step path of 0/1 children. Then for each number, walk down greedily always taking the opposite bit when that child exists, since a differing bit contributes 1 at that position and higher bits dominate.

$O(32n)$ instead of $O(n^2)$. Recognising that “prefix” can mean bit prefix, not just character prefix, is what unlocks a whole family of XOR problems.

8 problems

0 easy7 medium1 hard

Work down the ladder. Tick each problem off as you go — progress is saved in this browser, and the Export button in the filter bar writes it to a file you can keep.

AllEasyMediumHard

Unsolved onlyExportImportReset

• ○208Implement Trie (Prefix Tree)mediumThe base structure; the end-of-word marker is the whole pointNeetCode 150Blind 75LeetCode Top Interview 150googleamazonbloomberg
• ○211Design Add and Search Words Data StructuremediumWildcards turn the walk into a DFS; skip the marker keyNeetCode 150Blind 75LeetCode Top Interview 150
• ○421Maximum XOR of Two Numbers in an ArraymediumA **bitwise** trie -- insert 32-bit paths, then greedily take the opposite bit
• ○648Replace WordsmediumStop at the first marker to get the shortest root free
• ○677Map Sum PairsmediumStore a value per word; sum the whole subtree under a prefix
• ○720Longest Word in DictionarymediumA word qualifies only if **every** prefix is also a word -- check markers all the way down
• ○1268Search Suggestions SystemmediumWalk to each prefix, then collect the 3 lexicographically smallest below it
• ○212Word Search IIhardOne grid DFS carrying a trie node -- prunes against the whole dictionary at onceNeetCode 150Blind 75LeetCode Top Interview 150googleamazonbytedance

Dry run

LC 212 Word Search II is the problem this pattern exists for. Grid:

text

o a a n
e t a e
i h k r
i f l v

with words = ["oath", "pea", "eat", "rain"].

The naive approach runs a separate DFS per word: 4 words × 16 start cells × up to 4 directions per step. The trie approach walks the grid once, carrying a trie node alongside the position.

Start cell	trie node after	outcome
(0,0) o	root → o	o exists (prefix of “oath”) — continue
(0,0)→(1,0) e	o has no child e	prune immediately, whole branch dead
(0,0)→(0,1) a	o → a	continue
… → (1,1) t	oa → t	continue
… → (2,1) h	oat → h, is_word set	record “oath”
(0,1) a	root has no child a…	actually it does not — prune at depth 1
(1,0) e	root → e (prefix of “eat”)	continue
(1,0)→(1,1) t	e → t	continue
(1,1)→(1,2) a	et has no child a	prune

The point is the second row. A per-word DFS would have explored that entire subtree four separate times before failing. With a trie, one lookup that returns None kills the branch for every word simultaneously — and that is the difference between passing and a time-limit exceeded.

The optimisation interviewers actually want to hear

After recording a match, delete the word from the trie (or unset its flag and prune now-childless nodes). Otherwise a grid containing the same word many times re-explores it every time. This is the follow-up on LC 212, and it is what turns a just-passing solution into a comfortable one.

Interview follow-ups

They ask	What they’re checking	The answer
“Why a trie and not a hash set?”	Whether you know the actual win	A set matches exact lookup; a trie wins on prefix queries and on pruning a search against a whole dictionary
“Dict or a node class?”	Judgement	Dicts are shorter and interview-friendly; a class is more readable and avoids the marker-in-items() trap
“Why the end-of-word marker?”	Understanding vs. memorisation	It distinguishes “a word ends here” from “a word passes through here” — without it search("app") is wrong after inserting "apple"
“Space complexity?”	Precision	$O(n \cdot L \cdot \|\Sigma\|)$ worst case with array children; a dict makes it $O(\text{total characters})$ in practice
“Implement delete”	Depth	Clear the marker, then prune upward while a node has no children and no marker
“How does a trie help on LC 212?”	The key insight	One DFS carries a trie node; when the path leaves the trie, no word can match, so the branch dies immediately
“Compress it?”	Breadth	A radix tree / Patricia trie merges single-child chains; suffix automata and Aho-Corasick are the next tier for multi-pattern matching

Edge-case checklist

• Word that is a prefix of another — insert "apple" then check "app"; the reason the marker exists.
• Insert both "app" and "apple" — both markers must survive on the same path.
• Empty string — insert("") marks the root; decide whether that is legal and be consistent.
• Searching a longer word than anything stored — search("appl") and search("....") must be False.
• Searching a shorter pattern — search("b.") against 3-letter words is False; the end-of-pattern check must coincide with a marker.
• The marker key during wildcard iteration (LC 211) — skip it, or you will recurse into a boolean.
• Duplicate inserts — idempotent with this design; no special case needed.
• Characters outside the assumed alphabet — a dict handles them; a 26-slot array raises IndexError.

Self-check

pch.quizTag Trie patterns — self-check

1. Why is `is_word` a separate flag rather than just 'this node has no children'?

   A For speed B Because a word can terminate inside the path to a longer word — 'car' inside 'card' C To support deletion D It is redundant and can be dropped
   pch.quizShowAnswer

   B — Because a word can terminate inside the path to a longer word — 'car' inside 'card' — Leaf-ness and word-ness are different properties. Conflating them makes 'is car a word' unanswerable once 'card' is inserted, and it is the most common trie bug.

2. What does a trie buy over a hash set of words?

   A Faster exact lookup B Prefix queries — 'does any word start with this?' — which a hash set cannot answer without checking every word C Less memory in all cases D Nothing; a hash set is strictly better
   pch.quizShowAnswer

   B — Prefix queries — 'does any word start with this?' — which a hash set cannot answer without checking every word — For exact lookup a hash set is as fast and simpler. The trie earns its place the moment prefixes matter — autocomplete, or pruning a search — and Word Search II is entirely about that pruning.

3. In Word Search II, why is one grid DFS carrying a trie node better than one DFS per word?

   A It uses less memory B A single failed child lookup prunes the branch for every word at once, instead of once per word C It avoids recursion D It handles duplicate letters better
   pch.quizShowAnswer

   B — A single failed child lookup prunes the branch for every word at once, instead of once per word — This is the whole reason the problem is a trie problem. Per-word DFS re-explores the same dead-end subtrees once per word; the trie collapses all of those failures into one lookup returning None.

4. After finding a word in LC 212, what is the standard optimisation?

   A Restart the search from the next cell B Remove the word from the trie, so a grid containing it many times does not re-explore it C Cache the grid position D Sort the word list
   pch.quizShowAnswer

   B — Remove the word from the trie, so a grid containing it many times does not re-explore it — Unset the flag and prune now-childless nodes. Without it, a grid with the same word in twenty places pays the full search cost twenty times. This is the follow-up interviewers ask.

5. What is the space complexity of a trie holding n words of average length L?

   A O(n) — one node per word B O(n · L) worst case, but far less when prefixes are shared C O(L) — independent of the word count D O(n log L)
   pch.quizShowAnswer

   B — O(n · L) worst case, but far less when prefixes are shared — The worst case is no shared prefixes at all, giving one node per character. Real dictionaries share heavily, which is the whole point — but quote the worst case and then note the sharing.

Recall card

• Cue — many words plus a prefix question: autocomplete, wildcard search, or a grid/string search that should prune dead branches early.
• Structure — children: dict[str, Node] plus an is_word flag. Characters are on edges; nodes are positions in the shared prefix tree.
• Why not a hash set — a set answers exact membership just as fast. Only a trie answers “does any word start with this”, which is what makes pruning possible.
• Complexity — insert and search are $O(L)$, independent of how many words are stored. Space is $O(n \cdot L)$ worst case, much less with shared prefixes.
• Remember — is_word is not the same as “no children”; delete matched words in LC 212; carry the trie node alongside the DFS position rather than re-searching per word.
• Variants — wildcard . (branch to every child at that step, LC 211); binary trie over bits for maximum-XOR (LC 421); count-per-node for prefix counts.

Recap

• A trie stores words along shared character paths, making prefix queries $O(L)$ regardless of how many words are stored.
• node = node.setdefault(ch, {}) plus a "$" marker is a complete trie in six lines — no node class required.
• The end-of-word marker is what separates search from startsWith. Omitting it is the number-one trie bug.
• A wildcard turns the walk into a DFS that branches into every child — and you must skip the marker key while iterating.
• The biggest win is pruning: carrying a trie node through another search (a grid DFS, a recursion) kills branches that no dictionary word can extend, which is what makes LC 212 feasible.
• “Prefix” need not mean characters — a bitwise trie solves maximum-XOR problems in $O(32n)$.
• If you only need exact lookup, use a set. A trie earns its memory only when prefixes matter.

Next: the Search and Selection patterns — binary search on rotated arrays, quickselect, and heaps.