Design Add and Search Words Data Structure

Design a data structure that supports adding words and searching, where . can match any letter.

Function signature

type WordDictionary struct { /* fields */ }

func Constructor() WordDictionary
func (w *WordDictionary) AddWord(word string)
func (w *WordDictionary) Search(word string) bool

Inputs / outputs

• AddWord(word): insert a word.
• Search(word): return true if any stored word matches, where . matches any letter.

Example

AddWord("bad")
AddWord("dad")
Search("pad") -> false
Search("bad") -> true
Search(".ad") -> true
Search("b..") -> true

Constraints

• 0 <= number of operations <= 100_000
• words are lowercase a-z

Core idea (near-solution)

Use a trie. Normal characters follow a single child; . branches to all children with a DFS.

Invariant: DFS explores all possible matching paths for the wildcard.

Algorithm (step-by-step)

1. AddWord: insert the word into the trie and mark isWord at the end.
2. Search:
   • If the current char is a letter, follow that edge.
   • If the char is ., recursively try all non-nil children.
   • Succeed if any path reaches the end with isWord true.

Correctness sketch

• Invariant: DFS explores all possible matching paths for the wildcard.
• Each node represents a prefix; inserting builds all prefixes for a word.
• Searching follows the unique path for the word/prefix.
• Wildcards branch over all possible children, covering all matches.

Trace (hand walkthrough)

Example input:
AddWord("bad")
AddWord("dad")
Search("pad") -> false
Search("bad") -> true
Search(".ad") -> true
Search("b..") -> true

Walk:
- AddWord bad, dad -> trie has b->a->d and d->a->d
- Search "pad": no p child -> false
- Search "bad": exact path -> true
- Search ".ad": wildcard matches b or d -> true; "b.." matches b-a-d -> true

Pitfalls to avoid

• Treating . as a literal character instead of a wildcard.
• Returning true on a prefix match (must reach isWord).
• Exponential branching if you don't prune missing children quickly.

Complexity

• AddWord: O(L).
• Search: O(L) in best case, O(26^L) in worst case with many wildcards.

Implementation notes (Go)

• Use recursion for wildcard DFS; iterative stack is also fine.
• Children can be [26]*Node for fast traversal.