Add and Search Words Data Structure

Design a data structure called WordDictionary that stores lowercase words and supports wildcard searches.

Implement the behavior for:

WordDictionary(): Initializes an empty dictionary.
addWord(word): Adds word to the dictionary.
search(word): Returns true if any added word matches word. The . character can match any single lowercase letter.

Input & Output

Input

operations — operations to process; each row is `WordDictionary`, `addWord word`, or `search pattern`

Output

the return values of the search operations

Example

Input

operations = [
  WordDictionary
  addWord bad
  addWord dad
  addWord mad
  search pad
  search bad
  search .ad
  search b..
]

Output

false true true true

Explanation

`pad` has not been added, `bad` exists exactly, `.ad` can match `bad`, `dad`, or `mad`, and `b..` can match `bad`.

Constraints

Try it yourself