Design Add and Search Words Data Structure
Store words and search patterns where dot matches any one character.
Why does this pattern fit?
Restate the exact job
Store words and search patterns where dot matches any one character.
A wildcard branches across all children at exactly one depth.
O(L) add · O(b^w·L) worst search
A dot matches one character, not zero or many.
How to solve Design Add and Search Words Data Structure
The goal is to solve this problem from the pattern, not to memorize a finished answer. Use this as a check after your own attempt.
What the question asks
Store words and search patterns where dot matches any one character.
Why Tries & prefix search fits
A wildcard branches across all children at exactly one depth.
State to maintain
Trie node and pattern index.
Transition
Follow literal edges; on dot, recursively try every child for the next index.
Time and space
O(L) add · O(b^w·L) worst search
Counterexample to the tempting mistake
A dot matches one character, not zero or many.
Prove it again tomorrow
Close this page. Rebuild the state and transition from memory, write a test that exposes the mistake above, then solve a fresh input without looking back. A same-day reread is practice, not proof of retention.