Design Add and Search Words Data Structure

Medium

Problem

Design addWord(word) and search(word), where search's pattern may contain "." to match any single letter.

Example 1

Input:  addWord("bad"), addWord("dad"), addWord("mad"), search("pad"), search("bad"), search(".ad"), search("b..")
Output: false, true, true, true

Test cases

Case 1

Input:    new WordDictionary()
.addWord("bad")
.addWord("dad")
.addWord("mad")
.search("pad")
.search("bad")
.search(".ad")
.search("b..")
.search("b...")
Expected: [null,null,null,false,true,true,true,false]

Case 2

Input:    new WordDictionary()
.addWord("at")
.addWord("an")
.search("a.")
.search(".t")
.search("...")
Expected: [null,null,true,true,false]

Case 3

Input:    new WordDictionary()
.search("a")
.addWord("a")
.search(".")
.search("..")
Expected: [false,null,true,false]

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
View solutionHide solution1 approach

1. Trie + DFS on "."

Time add O(L); search O(L) without dots, up to O(26^L) worst caseSpace O(total characters)

Insert normally. When searching, a "." branches into every child; a letter follows one edge.

class WordDictionary {
constructor() { this.root = {}; }
addWord(word) {
let node = this.root;
for (const ch of word) node = node[ch] ??= {};
node.end = true;
}
search(word) {
const dfs = (node, i) => {
if (i === word.length) return !!node.end;
const ch = word[i];
if (ch !== '.') return !!node[ch] && dfs(node[ch], i + 1);
for (const k in node) if (k !== 'end' && dfs(node[k], i + 1)) return true;
return false;
};
return dfs(this.root, 0);
}
}