Design Add and Search Words Data Structure

medium

Support addWord and search with wildcard dot matching

Design Add and Search Words Data Structure

Key Insight

Literal characters use one trie child; "." wildcards branch to all children once at that level.

Step 1Add Dictionary Words
Array
bad
0
dad
1
mad
2
HashMap
b:1
d:1
m:1

Insert bad, dad, and mad into the trie.

1 / 3

Learn the Pattern

Hash MapUse a hash map for O(1) lookup to track seen elements, frequencies, or complement values during array traversal.
Practice the Code

Step-by-Step Walkthrough: Design Add and Search Words Data Structure

Literal characters use one trie child; "." wildcards branch to all children once at that level.

  1. Add Dictionary Words

    Insert bad, dad, and mad into the trie.

  2. Exact Match

    search("bad") follows a single path b-a-d and must land at terminal node.

  3. Wildcard Match

    search(".ad") branches at first char and validates all child options in parallel.