Medium

Quiz

#211 Design Add and Search Words Data Structure

APPROACH

Build a searchable word dictionary that supports wildcard patterns.

Implement WordDictionary:

- WordDictionary() creates the dictionary.

- void addWord(word) records word for future lookups.

- bool search(word) returns true if a stored word matches the pattern; dots '.' in the pattern match any single letter.

Example 1:

Input

["WordDictionary","addWord","addWord","addWord","search","search","search","search"]

[[],["bad"],["dad"],["mad"],["pad"],["bad"],[".ad"],["b.."]]

Output

[null,null,null,null,false,true,true,true]

Example 2:

Explanation

WordDictionary wordDictionary = new WordDictionary();

wordDictionary.addWord("bad");

wordDictionary.addWord("dad");

wordDictionary.addWord("mad");

wordDictionary.search("pad"); // return False

wordDictionary.search("bad"); // return True

wordDictionary.search(".ad"); // return True

wordDictionary.search("b.."); // return True

1 of 4

1:00

What is the optimal approach for this problem?