Design Add and Search Words Data Structure

Medium

Design a data structure with addWord(word) and search(word). In search, a . can match any single letter. search returns whether any added word matches.

Example 1

Input:  operations = ["WordDictionary","addWord","addWord","addWord","search","search","search","search"], values = [[],["bad"],["dad"],["mad"],["pad"],["bad"],[".ad"],["b.."]]
Output: [null,null,null,null,false,true,true,true]

Constraints

• 1 <= word.length <= 25
• Added words are lowercase letters; search words may contain ".".
• At most 10^4 calls.