Pattern this teaches:Trie
Design Add and Search Words Data Structure
A medium Trie interview guide. Task statement, worked examples, intuition, and step-by-step solutions.
- Topic
- Trie
- Sheets
- 2
- Core for
- 7 roles
The problem
Design a data structure that supports adding words and searching for words, where search queries may contain a dot '.' as a wildcard that matches any single lowercase letter.
Example 1
- Input
- addWord("bad"), addWord("dad"), addWord("mad"), search("pad"), search("bad"), search(".ad"), search("b..")
- Output
- false, true, true, true
Example 2
- Input
- addWord("a"), addWord("a"), search("a"), search("aa"), search("a.")
- Output
- true, false, true
Constraints
- Words consist of lowercase English letters
- '.' in search queries matches any single letter
- At most 10^4 calls in total
How to think about it
Updated 2026-09-29Exact characters dictate a deterministic single-step transition, while a wildcard forces the search to explore all existing outgoing edges at that step. Structuring the dictionary as a prefix tree isolates wildcard branching only to nodes where transitions actually exist, keeping search bounded by the valid dictionary branches.
Approaches, worst first
Word list regex matching
time O(n * L) · space O(total characters)
Store all words in an array or grouped by length. Convert wildcard queries into regular expressions and test against each stored candidate. Straightforward to implement, but scans every stored word on every wildcard query.
Trie with recursive branchingWrite this one
time O(26^d * L) · space O(total characters)
Build a trie for additions. On search, step deterministically for standard letters and branch across all non-null children whenever encountering a dot. The first branch returning true short-circuits the search.
Where people lose marks · 3
- Failing to short-circuit upon finding a match among child branches during wildcard traversal, doing redundant work across alternative branches.
- Assuming a dot matches empty strings: a wildcard must consume exactly one letter.
- Returning true at the end of the query string even if the landing trie node is not marked as the terminal character of a word.
The theory behind it
Trie — the ground this problem stands on. All Trie problems
What Trie is
A trie, also called a prefix tree, is a tree structured for storing words character by character. Instead of storing entire words in individual nodes, each step down a branch represents a single letter. Words that share the same beginning, like car, card, and care, share the exact same starting path down the tree. A special boolean marker sits at the end of each valid word to show that a complete word terminates at that letter.
When to reach for it
Reach for a trie when questions involve prefix lookups, dictionary word searches, autocomplete engines, or matching prefixes against a body of text. Prompts asking whether any word in a dictionary begins with a given prefix, or searching for words on a Boggle board grid, point directly to a trie. It also applies to bitwise tasks, such as finding the maximum XOR pair among integers by treating numbers as binary prefixes.
How the pattern works
Represent each trie node with an array or hash map of child links, plus a boolean flag marking if a complete word ends at that node. When inserting, start at the root and walk down character by character, creating new child nodes whenever a path does not exist yet, then mark the final node as a word ending. When searching, follow the characters; if any child link is missing, the word or prefix does not exist. If all characters match, check the boolean flag to distinguish between a full word and a partial prefix.
More Trie problems
Target Roles
Core requirement for 7 roles:
Track in your role's order
Pick your target role and all 370 problems resequence to what that interview actually asks.
Start freeProblem set and role mapping as of .