Skip to content
Onsite
2 / 4

Design Add and Search Words Data Structure

MediumP3Coding

Design a dictionary that supports adding words and searching with wildcards.

  • WordDictionary() creates an empty dictionary.
  • addWord(word) adds a lower-case word.
  • search(word) returns true if some stored word matches word. In word, the character . stands for any single letter. A match must have exactly the same length as word.

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]

Constraints

  • 1 <= word.length <= 25
  • addWord words are lower-case; search words are lower-case or contain '.'
  • At most 2 dots per search word
  • At most 10^4 calls in total

Hints

Run checks the 2 visible tests, Submit all 5.