Word Dictionary With Wildcard Search

Design a class WordDictionary that stores words and answers pattern searches:

• add_word(word) stores word (adding the same word twice has no extra effect).
• search(pattern) returns True if some stored word matches pattern exactly, where the character . in the pattern matches any single letter.

Examples

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

Constraints

• Words and patterns have length 1..25; words are lowercase letters; patterns are lowercase letters or .
• Up to 10**4 calls in total
• Target: add_word in O(len(word)); search explores only trie branches consistent with the pattern

Goals

• Store words in a trie inside a class
• Branch on every child when the pattern character is a wildcard