Design Add and Search Words Data Structure
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, trueTest 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]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); }}