Loading problem…
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.
Example 1
Input: operations = ["WordDictionary","addWord","addWord","addWord","search","search","search","search"], arguments = [[],["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.
Example 2
Input: operations = ["WordDictionary","addWord","search","search"], arguments = [[],["a"],["a"],["."]]
Output: [null,null,true,true]
Explanation: A single '.' matches the one-letter word 'a'.
Example 3
Input: operations = ["WordDictionary","addWord","search"], arguments = [[],["word"],["word"]]
Output: [null,null,true]
Explanation: "word" was added, so searching for exactly "word" returns true.
Store words in a trie exactly as usual. The only twist is the search: a '.' can be any letter, so at a dot we can't follow a single edge — we must try every child and succeed if any branch matches the rest of the pattern. That branching turns search from a straight walk into a depth-first search over the trie.
Run checks all cases above. Submit evaluates all test cases.