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.
• addWord(word) - adds word to the data structure; it can be matched later.
• search(word) - returns True if there is any string in the data structure that matches word, or False otherwise. word may contain dots '.' where dots can be matched with any letter.

---

Example 1

Input:
["WordDictionary","addWord","addWord","addWord","search","search","search","search"]
[[],["bad"],["dad"],["mad"],["pad"],["bad"],[".ad"],["b.."]]

Output:
[null, null, null, null, False, True, True, True]

Input: ops as above
Output: [null, null, null, null, False, True, True, True]
Explanation: "pad" was never added so search("pad") is False. search(".ad") matches "bad", "dad", or "mad". search("b..") matches "bad".

Example 2

Input: addWord("a"), search(".")
Output: True
Explanation: A single dot matches any single character, and "a" was added.

---

Constraints

• 1 <= word.length <= 25
• word in addWord consists of lowercase English letters only.
• word in search consists of '.' or lowercase English letters.
• There will be at most 2 dots in search.
• At most 10^4 calls will be made to addWord and search.