Design Add and Search Words Data Structure
MediumTries
Build a WordDictionary class that stores words and finds them, with two methods:
addWord(word) stores word. search(word) returns true if some stored word matches word, and false otherwise. In a search, a dot . matches any one letter; every other letter matches only itself, and the lengths must be equal.
Each test makes a new WordDictionary and calls its methods in order. The output lists what each call returns, with null for the constructor and for addWord.
Examples
Input: WordDictionary(), addWord("lamp"), addWord("lump"), search("l.mp"), search("lam"), search("...."), search(".")
Output: [null, null, null, true, false, true, false]l.mp matches both words; lam is only the start of one; .... matches any four-letter word, and no word has one letter.
Input: WordDictionary(), search("."), addWord("x"), search("."), search("..")
Output: [null, false, null, true, false]A dot needs a letter to match, so it finds nothing until x is added, and two dots never match one letter.
Constraints
1 ≤ word.length ≤ 25addWordgets lowercase English letters only;searchgets lowercase letters and dots.- At most 10⁴ calls in all.
Stuck?
Hint 1
Keep the words in a trie: a tree of letters where each node marks whether a word ends there.
Hint 2
Search letter by letter. At a letter, follow that one child. At a dot, try every child of the current node with the rest of the word, and succeed if any of them does.
The idea
Keep the words in a trie, a tree with a letter on each edge, so words that start the same share a path. A search follows the word down the tree. At a dot it cannot know which letter is meant, so it tries every branch and succeeds if any of them leads to a match.
Time O(L) for addWord; O(L) for a search without dots, more when dots make it try several branchesExtra space O(total letters added)
Try it again with the idea in mind, or go through the code one step at a time.
The code, step by step
Step 1 of 6
Each node maps a letter to the next node, and end marks a node where a stored word finishes. The root stands for the empty start of every word.
class WordDictionary { constructor() { this.root = { children: {}, end: false }; } addWord(word) { let node = this.root; for (const letter of word) { if (!node.children[letter]) node.children[letter] = { children: {}, end: false }; node = node.children[letter]; } node.end = true; } search(word) { const match = (node, i) => { if (i === word.length) return node.end; const letter = word[i]; if (letter === '.') { return Object.values(node.children).some((child) => match(child, i + 1)); } const child = node.children[letter]; return child !== undefined && match(child, i + 1); }; return match(this.root, 0); }}The trap
Following only the first branch at a dot gives up on every other letter. When that branch is a dead end and a later one matches, the search still answers false. A dot needs a search that can back up and try the next branch, which is why match calls itself.
class WordDictionary { constructor() { this.root = { children: {}, end: false }; } addWord(word) { let node = this.root; for (const letter of word) { if (!node.children[letter]) node.children[letter] = { children: {}, end: false }; node = node.children[letter]; } node.end = true; } search(word) { let node = this.root; for (const letter of word) { // at a dot, follows only the first child instead of trying each node = letter === '.' ? Object.values(node.children)[0] : node.children[letter]; if (!node) return false; } return node.end; }}