Design Add and Search Words Data Structure

Design a WordDictionary class that stores words and answers searches in which . acts as a wildcard.

• WordDictionary() creates an empty dictionary.
• addWord(word) stores word. Adding the same word twice has no extra effect.
• search(word) returns True if some stored word matches word, and False otherwise.

A stored word matches the search pattern when both have the same length and, at every position, the pattern either has the same letter or has ., which matches any single letter. A . never matches an empty position, so the lengths must be equal. Only words added before the search count.

The examples list the calls made in order, and the output lists each call's return value (None for the constructor and addWord).