Design Add and Search Words Data Structure in Python

Design a data structure that stores words and finds them again, where the word you search for may contain dots: a dot '.' matches any one letter.

Implement the class WordDictionary:

• WordDictionary() creates an empty dictionary of words.
• addWord(word) adds word to it.
• search(word) returns True if some added word matches word, and False otherwise. An added word matches when it has the same length and, at every position, the same letter as word; where word has a dot, any letter matches.

The input is a list of operations, applied in order to one new dictionary. The output lists what the search calls return, in order. The starter code spells these names the way your language does.

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 added. ".ad" matches "bad", "dad" and "mad", and "b.." matches "bad".

Example 2:

Input:
    addWord("a")
    addWord("ab")
    search(".")
    search("a.")
    search(".b")
    search(".a")
    search("..")
    search("b")
Output: True True True False True False
Explanation: "." matches the one-letter word "a", and "a.", ".b" and ".." all match "ab". No added word has "a" as its second letter, and "b" was never added.

Example 3:

Input:
    addWord("at")
    search("a")
    search("at.")
    search(".t")
    search("a..")
    search(".")
Output: False False True False False
Explanation: A dot stands for exactly one letter, never for none, so "at." and "a.." need a three-letter word and "." a one-letter word. "a" is the beginning of "at", but a search must match a whole word.

Constraints:

• 1 <= word.length <= 25
• A word passed to addWord consists of lowercase English letters, a to z.
• A word passed to search consists of lowercase English letters and dots, with at most 2 dots.
• At most 105 calls in total are made to addWord and search.