Insert and Search Words with Wildcards

Design a data structure that supports adding new words and then searching for a word, where the search word may contain the . wildcard character, which can match any single letter.

Implement:

• addWord(word): adds word to the dictionary.
• search(query): returns true if there is a word in the dictionary that matches query. query may contain the letters a-z and the character ., where each . may match any one letter. The matched word must be exactly the same length as query.

Example 1

dict = WordDictionary()
dict.addWord("bad")
dict.addWord("dad")
dict.addWord("mad")
dict.search("pad")   # -> false ("pad" was never added)
dict.search("bad")   # -> true
dict.search(".ad")   # -> true (matches "bad", "dad", or "mad")
dict.search("b..")   # -> true (matches "bad")
dict.search("b.d")   # -> true (matches "bad")
dict.search("...")   # -> true (any 3-letter word matches)
dict.search("....")  # -> false (no 4-letter word was added)

Constraints

• 1 <= word.length, query.length <= 25
• word consists of lowercase English letters.
• query consists of lowercase English letters and/or ..
• At most 10^4 calls total to addWord and search combined.
• At most 2 dots appear in any single search call in the worst realistic test cases, but your solution should handle more.