Design Add And Search Words Data Structure

Medium · Tries

Build a small word store that supports adding words and later checking whether a given pattern matches any stored word. A search pattern may contain the normal lowercase letters plus the wildcard character '.', which can stand for any single letter. Implement addWord to insert a word, and search to return true if some previously added word matches the pattern (matching means same length and every non-dot character matches exactly).

Examples

Input:  addWord("bad"); addWord("dad"); addWord("mad"); search("pad"); search("bad"); search(".ad"); search("b..")
Output: false, true, true, true
Why:    "pad" was never added so it fails; "bad" was added so it matches directly; ".ad" matches "bad", "dad" or "mad" since the dot can be any letter; "b.." matches "bad" since the dots cover 'a' and 'd'.

Input:  addWord("a"); search("a"); search("."); search("aa")
Output: true, true, false
Why:    "a" matches itself, the single dot matches the single letter 'a', but "aa" has a different length than the stored word so it fails.

Constraints

1 <= word.length <= 25 for addWord and search, words use only lowercase english letters, search patterns may also contain '.', at most 2*10^4 total calls to addWord and search

Practise it by voice

Describe the solution out loud and the interviewer writes exactly what you say, asks when you are vague, and runs the tests in your browser.

Practise Design Add And Search Words Data Structure

This statement is written for CodeSpeek. The problem is part of the NeetCode 150 list; Watch NeetCode's explanation of Design Add And Search Words Data Structure. Reference solutions from the NeetCode repository (MIT) are used to verify our tests.