166. Design Add and Search Words Data Structure

MediumDesign

Design a data structure that supports adding new words and finding if a string matches any previously added string. Implement the WordDictionary class: WordDictionary() initializes the object; addWord(word) adds word to the data structure; search(word) returns true if there is any string in the data structure that matches word, or false otherwise. word may contain dots '.' where a dot can match any single letter.

Examples

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]

Explanation: 'pad' was never added; '.ad' matches bad/dad/mad; 'b..' matches bad.

Constraints

  • 1 <= word.length <= 25; word in addWord consists of lowercase English letters; word in search consists of '.' or lowercase English letters; there will be at most 2 dots in word for search queries; at most 10^4 calls to addWord and search
Loading...

Run checks all cases above. Submit evaluates all test cases.