Design Add and Search Words Data Structure
On this page
Problem statement
Design a word dictionary with two operations.
addWord(word)stores a lowercase word.search(pattern)returns true if any stored word matches the pattern exactly, where each.in the pattern matches any single letter. The match must cover the whole word, not just a prefix.
A trie question with one twist: the wildcard turns a single walk down the tree into a small search over several branches. The same shape appears in autocomplete with typos, crossword solvers and log-pattern filters. Original problem: LeetCode 211.
Example

addWord("cache"); addWord("cast"); addWord("cat")
search("ca.") -> true # cat
search("c..t") -> true # cast
search(".a.he") -> true # cache
search("ca") -> false # "ca" is only a prefix
search("dog") -> false
Constraints (assumed)
- Words have 1 to 25 lowercase letters; up to 10⁴ calls.
- A pattern has at most 2 dots (the cost of a search grows with the number of dots).
What this question tests
- Choosing a trie so that words sharing a prefix share work.
- Turning the wildcard into a DFS / backtracking over children.
- The end-of-word flag: matching a prefix is not matching a word.
Questions to ask first
- What characters can appear? (Here: lowercase letters, plus
.in patterns.) - Must the pattern match the whole word? (Here: yes.)
- How many dots can a pattern have? That bounds the branching.
- Is it read-heavy or write-heavy? That decides whether to index words by length or build extra structures.
Try it yourself first
You have the full problem. Sketch your answer, then sign up free to read the complete walkthrough.
- The complete design, flow by flow, with pictures
- Deep dives into the hard parts
- What mid, senior and staff candidates are expected to say
- Full company question lists
Free forever. No card needed.