bad
inserted
Build a dictionary that stores words and answers searches where . matches any single letter. A trie handles the prefixes; DFS with backtracking handles the wildcard by trying every child at each ..
Implement addWord(word) and search(word). A search string may contain ., which matches any one letter. After adding "bad", "dad", "mad": search("pad") → false, search(".ad") → true, search("b..") → true.
. means "any child works," so you recurse into every child and succeed if anybranch reaches a word end. The recursion is the whole trick — it turns "try all possibilities" into a clean DFS.TrieNode has a children map (char → node) and an end flag — so we know where a real word stops.end = true on the final node. Pure prefix insertion, no recursion needed.i === word.length), return the current node's endflag — reaching a node isn't enough; it must be a word end.. wildcard. Recurse into every child; return true the moment one branch succeeds. If all fail, backtrack and report failure.node.end, not just true. Otherwise search("ba") would wrongly match after inserting only "bad"— you'd be at a valid node that isn't a complete word.addWord is always O(m) for a word of length m. search with no . is also O(m). But each . multiplies the branching factor by up to 26, so a pattern of all dots can explore O(26ᵐ) paths — bounded in practice by how many words actually share those prefixes. Space is O(total characters inserted).
addWord("bad") — walked/created 3 nodes (3 new) and marked the last as a word end.class TrieNode {
children: Map<string, TrieNode> = new Map();
end = false;
}
class WordDictionary {
private root = new TrieNode();
addWord(word: string): void {
let node = this.root;
for (const ch of word) { // walk, creating edges
let next = node.children.get(ch);
if (!next) {
next = new TrieNode();
node.children.set(ch, next);
}
node = next;
}
node.end = true; // mark a complete word
}
search(word: string): boolean {
const dfs = (node: TrieNode, i: number): boolean => {
if (i === word.length) return node.end; // consumed pattern → is it a word?
const ch = word[i];
if (ch === '.') { // wildcard: try EVERY child
for (const child of node.children.values()) {
if (dfs(child, i + 1)) return true;
}
return false; // no branch worked
}
const next = node.children.get(ch); // literal: one edge only
return next ? dfs(next, i + 1) : false;
};
return dfs(this.root, 0);
}
}children map and an end boolean. The map keys are single characters; end marks where an inserted word terminates.node.end = true. This is the ordinary trie insert — O(m) and no recursion.i === word.length means the whole pattern was consumed. Return node.end — being ata node isn't a match unless it's a complete word.., loop over node.children.values() and recurse one level deeper into each. The first branch that returns true short- circuits the rest; if none do, this . fails and we backtrack.falseimmediately — there's nothing to explore.addWord: O(m). search: O(m) with no dots, up to O(26ᵐ) when the pattern is all dots (each . branches into every child). Space: O(total characters stored).node.end and not true at the end?" Otherwise prefixes of stored words (e.g. "ba" for "bad") would falsely match..can fan out by 26 at each level → O(26ᵐ); in practice it's bounded by the words that share those prefixes.TrieNode[26] is faster and cache-friendly for lowercase a–z; a Map is cleaner for larger or unknown alphabets.* matched zero-or-more chars?"You'd add a branch that both stays at the node (consume the *) and descends without consuming — like regex/DP matching.| "search with . wildcards" | trie + DFS over children |
| hit a "." in the pattern | recurse into ALL children |
| pattern fully consumed | return node.end (not true) |
| many words, shared prefixes | trie to share nodes |
class TrieNode { children = new Map<string, TrieNode>(); end = false; }
addWord(w) { // plain trie insert
let n = root;
for (const c of w) { if (!n.children.has(c)) n.children.set(c, new TrieNode()); n = n.children.get(c); }
n.end = true;
}
search(w) {
const dfs = (n, i) => {
if (i === w.length) return n.end;
if (w[i] === '.') { for (const c of n.children.values()) if (dfs(c, i+1)) return true; return false; }
const nx = n.children.get(w[i]);
return nx ? dfs(nx, i+1) : false;
};
return dfs(root, 0);
}