Add and Search Word (Wildcards)

Add and Search Word — Data Structure Design medium

Description

Design WordDictionary:

addWord(word) — store a word.
search(word) — return true if any stored word matches word, where a . in the query matches any single letter.

Examples

> addWord("bad"); addWord("dad"); addWord("mad")
  search("pad")   -> false
  search("bad")   -> true
  search(".ad")   -> true     # matches bad, dad, mad
  search("b..")   -> true     # matches bad

Constraints

1 <= word.length <= 25
addWord words are lowercase letters; search words may contain .
at most 2 dots could still blow up if you’re naive — but length ≤ 25 keeps it bounded.

Intuition

addWord is plain trie insert. The twist is search: a . means “try every child.” That turns the linear walk into a DFS — at a normal character, descend the one matching child; at a ., recurse into all children. The recursion explores only the branches that could still match, so it stays efficient in practice.

Code

The wildcard is just “branch into all children.” Every trie search is secretly a DFS where each character picks one branch. A . simply lifts that restriction for one step. Recognizing that “search = DFS, exact char = one branch, wildcard = all branches” lets you extend the pattern to other matchers (?, *, character classes).

Analysis

Time: addWord is O(L). search is O(L) with no dots; worst case O(26^d · L) where d is the number of dots — bounded because word length ≤ 25 and real inputs have few dots.
Space: O(total characters added) for the trie, O(L) recursion depth.

Same skin

Implement Trie — this is that, with a DFS search.
Word Search II — the same “trie + DFS” idea, but the DFS walks a 2-D grid instead of a query string.
Regex / glob matching — . here is the simplest wildcard; the branching-DFS generalizes.

Implement Trie Replace Words