Add Words and Match Single-Character Wildcards

# Add Words and Match Single-Character Wildcards Implement a `WordDictionary` object that stores words and answers pattern queries. A query matches a stored word only when their lengths agree and every position matches. In a query, `.` matches exactly one arbitrary lowercase letter. ### Interface - `WordDictionary()` creates an empty object. - `void addWord(string word)` adds a lowercase word. - `bool search(string word)` returns whether the query matches at least one previously added word. ### Example 1 | Operation | Result | |---|---| | `WordDictionary()` | `null` | | `addWord("lake")` | `null` | | `addWord("late")` | `null` | | `search("la.e")` | `true` | | `search("l..e")` | `true` | | `search("lat")` | `false` | | `search("lane")` | `false` | `null` denotes construction or a void operation. The last query fails because neither stored word has `n` in its third position. ### Example 2 In a new empty object, `search(".")` is `false`. After adding `"a"`, `search(".")` is `true` and `search("..")` is `false`. After also adding `"to"`, `search("..")` becomes `true`. ### Constraints - `1 <= word.length <= 25` for both operations. - Added words contain only lowercase English letters. - Queries contain lowercase English letters and possibly `.`. - Each query contains at most two dots. - At most `10000` calls to `addWord` and `search` occur in total. ### Clarifications A dot is not an arbitrary-length substring wildcard. Queries do not insert words, and a prefix does not match a longer stored word. State persists between operations on one object; separate objects do not share words. ### What a Strong Answer Covers - Exact matching at the end of the pattern, including the difference between a prefix and a whole word. - How one or two wildcard positions affect the candidates that must be considered. - Queries on an empty dictionary and repeated additions. - Time and storage bounds using the maximum word length and wildcard count.