Add and Search Words With Wildcards

Build a word dictionary. Each operation is a string: "add w" stores the word w; "search p" asks whether some stored word matches the pattern p, where . matches any single letter and every other character matches itself (the word and the pattern must have the same length). Return the answers of all search operations, in order.

For ["add bad", "add dad", "add mad", "search pad", "search bad", "search .ad", "search b.."] the answer is [False, True, True, True].

Examples

Example 1

Input:

run_word_dictionary(['add bad', 'add dad', 'add mad', 'search pad', 'search bad', 'search .ad', 'search b..'])

Output:

[False, True, True, True]

Example 2

Input:

run_word_dictionary(['search a'])

Output:

[False]

Constraints

• 0 <= len(ops) <= 20000
• Words and patterns are lower-case letters (patterns also .), 1 to 12 long.