Wildcard Keyword Lookup
A content-moderation service stores a blocklist of keywords and must answer membership queries where a '.' matches any single character. Design the structure so both adds and wildcard lookups stay fast.
Problem
Design a data structure that supports two operations: addWord(word) inserts a lowercase word, and search(word) returns true if any stored word matches the query. In a query, a '.' may match any single letter; all other characters must match exactly.
Input
A sequence of operations. addWord receives a lowercase word (1 ≤ length ≤ 25). search receives a pattern of lowercase letters and '.' (1 ≤ length ≤ 25). Up to 10^4 calls total.
Output
For each search call, a boolean.
Constraints
- Stored words and queries contain only lowercase letters; queries may also contain '.'
- '.' matches exactly one character — not zero, not many
- Lengths must match for a word to be a candidate
Examples
Example 1
Input
addWord("bad"); addWord("dad"); search("b.d")Output
true
'b.d' matches 'bad' (the dot matches 'a').
Example 2
Input
addWord("bad"); search("b..")Output
true
Both dots match, so 'b..' matches the 3-letter word 'bad'.