Build a word store, WordDictionary, that remembers words and answers lookups written as patterns.
WordDictionary() creates an empty store.addWord(word) stores word. Storing the same word again changes nothing.search(word) returns true if at least one stored word matches the pattern word, and false otherwise.A pattern is made of lower-case letters and dots. A dot . stands for any one letter; every letter must equal the letter in the same place. A match covers the whole stored word, so the pattern and the word must have the same length: "c.t" matches "cat" and "cut", but not "ca" or "cats".
Each example lists the calls in the order they are made (the first one creates the object), then each call's arguments, then what each call returns: null for the constructor and for addWord.
Example 1
Input:
["WordDictionary","addWord","addWord","addWord","search","search","search","search","search"]
[[],["lamp"],["lump"],["limb"],["l.mp"],["lamb"],["l..b"],[".."],["lam"]]
Output: [null,null,null,null,true,false,true,false,false]
l.mp matches both lamp and lump. Nobody stored lamb, so it is not found even though lamp differs from it in one letter. l..b matches limb. No stored word has two letters, so .. finds nothing, and lam is only the start of lamp, not a stored word.
Example 2
Input:
["WordDictionary","search","addWord","search","search","addWord","search","search"]
[[],["."],["sky"],["s.y"],["sky."],["skye"],["sky."],["..y"]]
Output: [null,false,null,true,false,null,true,true]
The first search runs on an empty store. sky. needs a four-letter word, so it fails until skye is added, and then succeeds.
Example 3
Input:
["WordDictionary","addWord","addWord","search","search","search"]
[[],["go"],["go"],["o."],[".o"],["g"]]
Output: [null,null,null,false,true,false]
Adding go twice keeps one copy. The dot can stand for a letter at any position, but the other letters must still line up: o. would need a word starting with o.
Constraints
1 <= word.length <= 25word in addWord is made of lower-case English letters.word in search is made of lower-case English letters and ..search pattern holds at most 2 dots.10⁴ calls are made in total to addWord and search.Comparing a pattern with every stored word repeats the same letter checks over and over. Store the words in a trie, so words that start the same share one path and a lookup follows the pattern one letter at a time.
Without dots this is a plain set: store each word, and a search asks whether that exact string is in it. The dot is what makes it a design problem. A pattern like "c.t" isn't one string to look up but up to 26 of them, and two dots make up to 676.
Time addWord O(L); search O(L) without dots, at most O(26^d · L) with d dotsSpace O(26 · N)
The full walkthrough and code are part of Premium
["WordDictionary","addWord","addWord","addWord","search","search","search","search","search"] [[],["lamp"],["lump"],["limb"],["l.mp"],["lamb"],["l..b"],[".."],["lam"]]
[null,null,null,null,true,false,true,false,false]