#235MediumTries· Wildcard Search

Word Filter Dictionary

A crossword helper stores a growing list of dictionary words. The player types a pattern where known letters are written as they are and every unknown letter is written as `.` (a dot). The helper must say whether at least one stored word has the same length as the pattern and fits it letter by letter. Design a class `WordDictionary`: - `WordDictionary()` creates an empty dictionary. - `addWord(word)` stores a word (adding the same word again changes nothing). - `search(pattern)` returns `true` when some stored word matches the pattern. A dot matches exactly one arbitrary letter, and a match must cover the entire word.

Input format

`operations`: the method names in call order (the first is the constructor); `arguments`: the argument list of each call.

Output format

One value per operation: `null` for the constructor and `addWord`, and a boolean for each `search`.

Examples

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

Output: [null, null, null, null, false, true, true, true]

pad was never stored. bad was. The pattern .ad fits bad, dad and mad, and b.. fits bad.

Input: operations = ["WordDictionary", "search", "addWord", "search", "search", "search"], arguments = [[], ["."], ["a"], ["."], [".."], ["a"]]

Output: [null, false, null, true, false, true]

Nothing is stored at first, so even a single dot fails. After adding a, one dot matches it, two dots do not (the lengths differ) and the exact pattern a matches.

Constraints

1 <= word.length, pattern.length <= 25
`word` uses lowercase English letters; `pattern` uses lowercase letters and `.`.
At most 10^4 calls in total.

Study first

Tries (Prefix Trees)

#trie
#design
#strings
#wildcard
#dfs