Design Add and Search Words
Design a data structure that stores words and answers searches in which some letters may be unknown. Implement a class WordDictionary with:
constructor(): creates an empty dictionary.addWord(word): storesword.search(word): returnstrueif some stored word matchesword, andfalseotherwise. In the search string, a dot.matches any single letter; every other character must match exactly. A match must have the same length as the stored word.
Each test creates a WordDictionary, calls the methods in the order shown, and compares the return value of every search (addWord returns nothing, shown as null, and isn't checked).
Constraints
1 <= word.length <= 25- Words passed to
addWordcontain lowercase English letters only. - Search strings contain lowercase English letters and dots.
- At most
10^4calls in total.
Examples
Example 1
Input: ["WordDictionary","addWord","addWord","addWord","search","search","search","search"]
[[],["cat"],["cut"],["dog"],["c.t"],["..g"],["ca"],["...."]]
Output: [null,null,null,null,true,true,false,false]"c.t" matches cat and cut, "..g" matches dog. "ca" is only a prefix, and no word has four letters.
Example 2
Input: ["WordDictionary","search","addWord","search","search"]
[[],["."],["a"],["."],[".."]]
Output: [null,false,null,true,false]A dot must match exactly one letter: "." fails on an empty dictionary, then matches "a"; ".." needs two letters.
Example 3
Input: ["WordDictionary","addWord","addWord","addWord","search","search","search"]
[[],["ab"],["ac"],["bd"],[".d"],[".c"],[".e"]]
Output: [null,null,null,null,true,true,false]For ".d" the search first tries the a branch, finds no d after it, backs up and succeeds through b.
Each test creates the class with the first operation, then calls the methods in order. Output lists what each call returns; null marks the constructor and methods that return nothing, and their return values aren't checked.
JavaScript you'll use: Classes for data structures Map and Set Recursion, the call stack and memoization
class WordDictionary {
constructor() {
}
/**
* @param {string} word
* @return {void}
*/
addWord(word) {
}
/**
* @param {string} word may contain '.' for any single letter
* @return {boolean}
*/
search(word) {
}
}
Ctrl/⌘ + ' runs the examples, Ctrl/⌘ + Enter submits. Use console.log freely: output shows under Console. In the editor, press Esc then Tab to move focus out.