Design Add and Search Words Data Structure

Implement a WordDictionary class:

• WordDictionary() creates an empty dictionary
• add_word(word) stores word
• search(pattern) returns True if some stored word matches pattern, where . matches any single letter. Lengths must match.

Example 1

Input:
["WordDictionary", "add_word", "add_word",
 "add_word", "search", "search", "search",
 "search"]
[[], ["bad"], ["dad"], ["mad"], ["pad"],
 ["bad"], [".ad"], ["b.."]]
Output:
[None, None, None, None, False, True,
 True, True]

Example 2

Input:
["WordDictionary", "add_word", "add_word",
 "search", "search", "search", "search"]
[[], ["a"], ["ab"], ["."], [".."], ["..."],
 [".a"]]
Output:
[None, None, None, True, True, False, False]

Example 3

Input:
["WordDictionary", "search"]
[[], ["."]]
Output:
[None, False]

Constraints

• 1 ≤ word length ≤ 25
• words: lowercase letters; patterns: lowercase letters and .
• at most 3 dots per search pattern
• up to 10⁴ calls in total