Tries · LC #211

Add and Search Words

Extend a trie to support wildcard search where `.` matches any single character, requiring DFS over all children at wildcard positions.

mediumLC #211AMZ★★GOO★META★MSFT★
Mark as done
Confidence
Ask GPTPractice

Statement

Problem & Approach

Problem statement, sample I/O, and key reasoning.

Design a data structure supporting `addWord(word)` and `search(word)` where `word` may contain `.` which matches any single letter.

Sample I/O

WordDictionary wd = new WordDictionary();
wd.addWord("bad"), wd.addWord("dad"), wd.addWord("mad")
wd.search("pad") → false
wd.search("bad") → true
wd.search(".ad") → true
wd.search("b..") → true

Intuition

How to Think About It

Intuition

A standard trie handles addWord identically to Implement Trie. The only difference is search: when the current character is `.`, we must try every existing child (DFS/backtracking) instead of following a single deterministic path.

Core Concept

Build a trie as in LC 208. For search, use a recursive DFS helper `dfs(word, idx, node)`: at a literal character follow that child; at `.` iterate all non-null children and recurse into each. Return true if any branch reaches the end with `isEnd = true`.

When to use

Pattern matching against a stored dictionary where patterns may contain single-character wildcards - e.g., spell-checker suggestions, regex-lite lookups.

When NOT to use

When wildcard patterns are complex (multi-char `*`, character classes) - use a full regex engine or Aho-Corasick instead. Also avoid when dictionary is tiny - a simple O(N·L) linear scan suffices.

Key Insights

What to Know Cold

  • The `.` wildcard forces branching: at each `.`, fan out to all 26 possible children - this is the only difference from standard trie search.
  • Early termination on null children prunes most branches; in practice performance is much better than the O(26^m) worst case.
  • The recursive DFS naturally handles mixed patterns like "a.p.e" by alternating deterministic and wildcard steps.
  • A word consisting entirely of dots (e.g., "...") checks all trie paths of that exact depth - worst case.
  • Can be optimised with iterative DFS + explicit stack to avoid recursion stack overflow on very long words.

1 example

Worked Examples

Wildcard mid-word and trailing dots

Search ".ad" and "b.." after inserting "bad", "dad", "mad"

At index 0, "." fans out to all children (b,d,m). For "b..", follows "b" then fans out at both dots.

const wd = new WordDictionary();
["bad","dad","mad"].forEach(w => wd.addWord(w));
wd.search(".ad"); // true - 'b','d','m' all match the dot
wd.search("b.."); // true - b→a→d path exists
wd.search("pad"); // false - 'p' child does not exist

Shows the DFS branching cost of wildcards and why all-dot patterns are worst case.