Word Dictionary with Wildcard Search
A search service stores words and answers membership queries where '.' in a query matches any single character. Design the data structure to add words and run these wildcard lookups efficiently.
Problem
Design a data structure supporting two operations: addWord(word) inserts a word, and search(query) returns true if any stored word matches the query, where '.' matches any single character. All other characters must match exactly and lengths must be equal.
Input
A sequence of operations: addWord(string) and search(string with letters and '.').
Output
For each search, a boolean indicating whether a match exists.
Constraints
- 1 <= word.length, query.length <= 25
- word consists of lowercase letters; query of lowercase letters and '.'
- At most 10^4 calls to addWord and search.
Examples
Example 1
Input
addWord("bad"); addWord("dad"); search("pad"); search(".ad"); search("b.."); Output
[false, true, true]
'pad' is absent; '.ad' matches bad/dad; 'b..' matches bad.
Example 2
Input
addWord("a"); search("a."); search(".")Output
[false, true]
'a.' has length 2 (no match); '.' matches the single 'a'.