Design Add and Search Words
Design Add and Search Words is a medium Tries problem from the Blind 75. The key pattern is trie + wildcard dfs, and a good solution runs in O(L) add; worst case grows with each dot time.
Problem
Process add and search operations where a dot in a search pattern matches exactly one lowercase letter.
Examples
Example 1
Input
[["add","map"],["add","mop"],["search","m.p"],["search","..p"]]Output
[true,true]Example 2
Input
[["add","cat"],["add","cot"],["add","cut"],["search","pat"],["search","cot"],["search",".ut"],["search","c.."]]Output
[false,true,true,true]Example 3
Input
[["search","a"]]Output
[false]Approach
Store words in a trie. A dot in a search tries every child at that position, so search becomes a depth-first walk.
| Pattern | Trie + wildcard DFS |
|---|---|
| Time | O(L) add; worst case grows with each dot |
| Space | O(total characters) |
Watch out for
A dot matches exactly one letter, never zero letters.