191. Design Add and Search Words Data Structure
Build a dictionary that supports wildcard lookups. Implement a WordDictionary class with two methods: add_word(word) (addWord in C++/Java) stores a word, and search(pattern) returns true if any previously stored word matches pattern.
A pattern is matched character by character: a lowercase letter must match itself, and a dot . matches any single letter. Lengths must line up exactly — "b.." matches only stored words of length 3 that begin with b.
Your class is driven by a scripted list of operations read from input. For every search call, print the boolean it returns — true or false, one per line, in call order.
Example 1:
Input: addWord("bad"), addWord("dad"), addWord("mad"), search("pad"), search("bad"), search(".ad"), search("b..")
Output: [false, true, true, true]
Explanation: "pad" was never stored. "bad" was. ".ad" matches bad, dad, and mad through its wildcard first letter, and "b.." matches bad.
Example 2:
Input: addWord("a"), addWord("ab"), search("a"), search("a."), search("."), search(".."), search("...")
Output: [true, true, true, true, false]
Explanation: Lengths must match exactly: "." can only match the one-letter word "a", ".." only "ab", and no stored word has three letters.
Constraints:
- 1 ≤ q ≤ 3 * 10⁴ operations in total
- 1 ≤ w.length, p.length ≤ 25
- Added words use lowercase letters a–z only; patterns use lowercase letters and '.'
- A pattern contains at most 3 dots.
- The same word may be added more than once.
Hints:
Group stored words by length. A search only needs to test words of exactly the pattern's length, comparing position by position and letting '.' accept anything. What does each search cost as the dictionary grows?
Store the words in a trie instead. A concrete letter follows one child edge as usual; a '.' forks the walk into every existing child. Do it as a DFS over (trie node, pattern position) — dead branches die instantly because missing children return false.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: addWord("bad"), addWord("dad"), addWord("mad"), search("pad"), search("bad"), search(".ad"), search("b..")
Expected output: [false, true, true, true]