Design Add and Search Words Data Structure
The problem
Support adding lowercase words and searching patterns where a dot matches exactly one arbitrary letter. A search succeeds if any stored word matches the entire pattern.
Example
After adding "cat" and "cut": search("c.t") → true; search("c..s") → false
Need a hint?
A normal character chooses one edge; a wildcard may branch.
Write pseudocode, trace the example, or note an edge case. This scratchpad does not run code.
Notes stay in this browser when storage is available.
Read the solution approach
Store words in a trie. Search recursively with a node and pattern index. For a letter follow its edge; for a dot try every child. At the pattern’s end, require an end-of-word marker. Return as soon as one branch succeeds.
Complexity
Insertion O(L); search visits up to all matching trie paths, exponential in wildcard count in the worst case. Space is trie size plus O(L) search stack.
Before moving on, explain why the algorithm is correct and trace a boundary case without looking at the approach.