-
Notifications
You must be signed in to change notification settings - Fork 0
092 — Design Add and Search Words Data Structure
LeetCode 211 · Medium. Design a data structure supporting addWord(word) and search(word), where search may contain . characters that each match any single letter — e.g. after adding "bad", "dad", and "mad", search(".ad") should return true.
This is Implement Trie's cousin with one twist: the search string can lie to you. A . doesn't commit to any particular character — it means "try every child here and see if any of them leads to a match." So you can't just walk a single path down the trie anymore the way plain search does; the moment you hit a ., the walk forks into as many branches as there are children at that node, and you need at least one of those branches to succeed. That's no longer a straight-line walk — it's a search tree of possibilities, explored with backtracking.
". matches any letter" / wildcard search over previously added words is the cue. Exact-match trie search is a single deterministic path; introducing a wildcard breaks that determinism and forces a recursive/backtracking search that tries every child branch at each . position, backtracking out of dead ends. Any time a "search" operation has to explore multiple possibilities instead of following one fixed path, that's DFS/backtracking layered on top of whatever structure you're searching.
Store every added word in an array. To search, compare the query against every stored word position by position, treating . as an automatic match — this is essentially manual wildcard/regex matching repeated once per stored word.
class WordDictionaryBruteForce {
private var words: [String] = []
func addWord(_ word: String) {
words.append(word)
}
func search(_ word: String) -> Bool {
let queryChars = Array(word)
for candidate in words where candidate.count == queryChars.count {
let candidateChars = Array(candidate)
var matches = true
for i in 0..<queryChars.count {
if queryChars[i] != "." && queryChars[i] != candidateChars[i] {
matches = false
break
}
}
if matches { return true }
}
return false
}
}
// smoke test
let bfDict = WordDictionaryBruteForce()
["bad", "dad", "mad"].forEach { bfDict.addWord($0) }
print(bfDict.search("pad")) // false
print(bfDict.search("bad")) // true
print(bfDict.search(".ad")) // true — "." matches 'b', 'd', or 'm'
print(bfDict.search("b..")) // true — matches "bad"Big-O: addWord is O(m). search is O(n · m) in the worst case — every one of the n stored words of matching length gets compared character by character against the m-length query.
Store words in a trie exactly like chapter 91. search walks it recursively: on a normal character, follow the single matching child (or fail if none exists); on ., recurse into every child and succeed if any branch succeeds.
final class WordNode {
var children: [Character: WordNode] = [:]
var isEndOfWord = false
}
final class WordDictionary {
private let root = WordNode()
func addWord(_ word: String) {
var node = root
for char in word {
if let next = node.children[char] {
node = next
} else {
let next = WordNode()
node.children[char] = next
node = next
}
}
node.isEndOfWord = true
}
func search(_ word: String) -> Bool {
let chars = Array(word)
func dfs(_ index: Int, _ node: WordNode) -> Bool {
if index == chars.count {
return node.isEndOfWord
}
let char = chars[index]
if char == "." {
for child in node.children.values {
if dfs(index + 1, child) { return true }
}
return false
} else {
guard let next = node.children[char] else { return false }
return dfs(index + 1, next)
}
}
return dfs(0, root)
}
}
// smoke test
let dict = WordDictionary()
["bad", "dad", "mad"].forEach { dict.addWord($0) }
print(dict.search("pad")) // false — no child 'p' at the root
print(dict.search("bad")) // true — exact path b -> a -> d, end-of-word
print(dict.search(".ad")) // true — '.' branches into b/d/m, 'b' -> a -> d succeeds
print(dict.search("b..")) // true — 'b' fixed, then '.' branches twice, a -> d matches
print(dict.search("a")) // false — no word of length 1, and no child 'a' at root anywayBig-O: With m = query length and no wildcards, search is O(m) — same as a plain trie walk. With wildcards, worst case (all .) is O(children^m) in the number of branches explored, though in practice it's bounded by however many actual words share those prefixes — far better than re-scanning all n stored words when prefixes diverge early. addWord remains O(m).
The brute force re-derives "does this word match, wildcards and all" from scratch for every single stored word, so cost scales with n. The optimal trie removes that duplication the same way chapter 91 did — shared prefixes are walked once — but adds one more move: at a ., instead of picking one child like exact search does, the DFS tries all of them and backtracks if a branch dead-ends. It's still fundamentally a trie walk; the only change is that the walk is no longer forced to be a single deterministic path, because the query itself is ambiguous at wildcard positions.
-
Tries — the underlying storage structure;
addWordis identical to chapter 91'sinsert. -
DFS and Backtracking — the wildcard
searchis a textbook backtracking search: at each., branch into every child, recurse, and backtrack out of any branch that fails without disturbing the others.
A . in the query turns a straight-line trie walk into a fork in the road — try every branch, and succeed the moment any one of them reaches the end as a real word.
Given the trie built from "bad", "dad", "mad", trace dfs for search("..d") step by step: at index 0, which children does the . branch into, and at index 1 (also .), which children does each of those branch into in turn? Then explain why search("....") (four dots) correctly returns false for this dictionary even though every stored word is checked via wildcard branching — what specifically causes every branch to fail?
⬅️ Previous: Implement Trie (Prefix Tree) · Next: Word Search II ➡️