Design Add and Search Words Data Structure

Design a data structure that supports adding new words and finding if a string matches any previously added string.

Implement the WordDictionary class:

• WordDictionary() Initializes the object.
• void addWord(word) Adds word to the data structure, it can be matched later.
• bool search(word) Returns true if there is any string in the data structure that matches word or false otherwise. word may contain dots '.' where a dot can represent any one letter.

Example:

WordDictionary wordDictionary = new WordDictionary();
wordDictionary.addWord("bad");
wordDictionary.addWord("dad");
wordDictionary.addWord("mad");
wordDictionary.search("pad"); // false
wordDictionary.search("bad"); // true
wordDictionary.search(".ad"); // true
wordDictionary.search("b.."); // true

Constraints:

• 1 <= word.length <= 25
• word in addWord consists of lowercase English letters.
• word in search consists of lowercase English letters or '.'.
• At most 2 dots '.' may appear in any search query.
• At most 10⁴ calls in total will be made to addWord and search.