Design Add and Search Words Data Structure
Design a word store that supports two actions: addWord(word) saves a word, and search(word) says whether any saved word matches. The twist is that a search string may contain the character a dot "." , which stands for any single letter . So ".ad" matches "bad", "dad" and "mad". Store the words in a trie. A normal letter follows exactly one link; a dot means you must try every link at that node and succeed if any one of them leads to a match. That "try each and stop on the first success" pattern is called backtracking. Because a class cannot be written down as plain data, this exercise uses the usual interview convention for design questions: you are handed a list of operation names and a matching list of argument lists, and you return the list of results. The constructor and addWord both produce null; search produces true or false.
Constraints
- 1 ≤ word.length ≤ 25
- addWord uses only lowercase English letters
- search uses lowercase English letters and dots, with at most 2 dots
- At most 104 calls in total to addWord and search
Example
operations = ["WordDictionary", "addWord", "addWord", "addWord", "search", "search", "search", "search"], args = [[], ["bad"], ["dad"], ["mad"], ["pad"], ["bad"], [".ad"], ["b.."]][null, null, null, null, false, true, true, true]Explanation "pad" was never added so it is false. "bad" was added so it is true. ".ad" matches "bad", "dad" and "mad", and "b.." matches "bad", so both are true.
In plain terms
- Wildcard
- A placeholder character that stands for something else. Here the dot "." stands for any one letter.
- Backtracking
- Trying one option, and if it fails, going back and trying the next one. A dot makes the search try every possible next letter in turn.
- Recursion
- A function that calls itself on a smaller piece of the problem. Here the matcher calls itself on the next node and the next character position.
Matching the pattern ".ad" against a trie of bad, dad and mad
After adding bad, dad and mad, the root has three child letters: b, d and m.
What happens in this step
added: 'bad', 'dad', 'mad'
root.children = { b, d, m }
search('.ad') starts with match(root, 0)
Each of the three words is its own three-letter path down from the root.Steps to visualize
- The row of cells is the pattern being matched: the root, then one cell per character of ".ad".
- The value shows what happened at that step of the match: which branch was taken, or whether the node was an end of word.
- A dot makes the matcher try every child letter in turn; the first branch that leads to a full match wins.
- The match only succeeds if the pattern runs out exactly on a node that is an end of word.
Walk through the code
Same walkthrough, now with the code. Press Next to move one step and watch which lines run.
After adding bad, dad and mad, the root has three child letters: b, d and m.
What happens in this step
added: 'bad', 'dad', 'mad'
root.children = { b, d, m }
search('.ad') starts with match(root, 0)
Each of the three words is its own three-letter path down from the root.Solution
function runWordDictionaryOperations(operations, args) {
class TrieNode {
constructor() {
this.children = {};
this.isEnd = false;
}
}
class WordDictionary {
constructor() {
this.root = new TrieNode();
}
addWord(word) {
let node = this.root;
for (const ch of word) {
if (!node.children[ch]) {
node.children[ch] = new TrieNode();
}
node = node.children[ch];
}
node.isEnd = true;
return null;
}
search(word) {
const match = (node, i) => {
if (i === word.length) {
return node.isEnd;
}
const ch = word[i];
if (ch === '.') {
for (const key of Object.keys(node.children)) {
if (match(node.children[key], i + 1)) {
return true;
}
}
return false;
}
const child = node.children[ch];
return child ? match(child, i + 1) : false;
};
return match(this.root, 0);
}
}
const results = [];
let dict = null;
for (let i = 0; i < operations.length; i++) {
const name = operations[i];
if (name === 'WordDictionary') {
dict = new WordDictionary();
results.push(null);
} else if (name === 'addWord') {
results.push(dict.addWord(args[i][0]));
} else {
results.push(dict.search(args[i][0]));
}
}
return results;
}- Time
- O(L) for addWord, and up to O(26^d * L) for a search with d dots
- Space
- O(total letters added)
Test cases
| Input | Expected | Covers |
|---|---|---|
operations = ["WordDictionary", "addWord", "addWord", "addWord", "search", "search", "search", "search"], args = [[], ["bad"], ["dad"], ["mad"], ["pad"], ["bad"], [".ad"], ["b.."]] | [null, null, null, null, false, true, true, true] | example from the docstring |
operations = ["WordDictionary", "search", "search"], args = [[], ["a"], ["."]] | [null, false, false] | nothing was added, so even a wildcard matches nothing |
operations = ["WordDictionary", "addWord", "search", "search"], args = [[], ["abc"], ["..."], [".."]] | [null, null, true, false] | a pattern of only dots must also match the right length |
operations = ["WordDictionary", "addWord", "search", "search"], args = [[], ["apple"], ["app"], ["apple"]] | [null, null, false, true] | a prefix of a stored word is not itself a match |
operations = ["WordDictionary", "addWord", "addWord", "search"], args = [[], ["ab"], ["ab"], ["a."]] | [null, null, null, true] | adding the same word twice is harmless |
operations = ["WordDictionary", "addWord", "addWord", "search", "search"], args = [[], ["at"], ["and"], [".n."], ["a."]] | [null, null, null, true, true] | a wildcard branch that dead-ends and one that succeeds |