Design Add and Search Words Data Structure

Design a word dictionary that supports adding words and searching with . as a wildcard matching any single lowercase letter.

Why this is worth learning

A dot means exactly one character, not any-length text. Searching is a DFS over (trie node, pattern position); a literal has one possible edge and a wildcard may branch.

Before coding: one-minute experiment

After adding bad, dad, and mad, which of .ad, b.., .., and b... match? Why is dot not equivalent to a regular-expression star?

Function signature

type WordDictionary struct { ... }
func Constructor() WordDictionary
func (w *WordDictionary) AddWord(word string)
func (w *WordDictionary) Search(word string) bool

Inputs / outputs

• word: lowercase English word or search pattern.
• . in search patterns matches any one character.
• Return: true if any added word matches the pattern exactly.

Example

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

Constraints

• Words contain lowercase English letters.
• Search patterns may contain . wildcards.
• Empty words/patterns are supported: AddWord("") marks the root terminal, and Search("") checks that flag. Construct each dictionary with Constructor.

Core idea (near-solution)

A direct wildcard query compares the pattern against every stored word of the right length. A trie shares the common-prefix work among candidates. A literal chooses one child; a dot means any one existing child, so the recursive result is the OR of their remaining-pattern answers. Failure of one child is not failure of all children. Reaching the pattern's end succeeds only at a terminal, preserving exact length. A dot consumes exactly one letter, unlike a star that could require a different state transition.

Invariant: dfs(node, i) returns true if some word under node matches pattern[i:].

Algorithm (step-by-step)

1. Insert words exactly as in a normal trie.
2. For search, define DFS over (node, index).
3. If index reaches the pattern length, return whether node is terminal.
4. If the current character is a letter, recurse into that child only.
5. If the current character is ., recurse into every existing child and return true on the first match.

Correctness sketch

The search state represents words whose prefix matches exactly the consumed pattern prefix. A literal transition preserves this fact only through its matching child. A dot transition explores every existing one-character child, covering all and only possibilities for that position. At the end of the pattern, accepting only a terminal node enforces exact length and complete-word membership. Induction on the remaining pattern length proves the returned disjunction is true exactly when an inserted word matches. Search reads but does not consume terminal markers, so repeated queries remain consistent.

Trace (hand walkthrough)

Pattern b..
root --b--> node b
wildcard tries child a
wildcard tries child d
index at end and d is terminal -> true

Pitfalls to avoid

• Letting . match zero or multiple characters; it matches exactly one.
• Returning true at the end of a prefix that is not a complete word.
• Searching all children for normal letters.

Debugging lens

At pattern exhaustion, check end rather than merely a non-nil node. Avoid creating children during search. Test a wildcard before a missing suffix and repeated identical searches.

Complexity

Insertion takes O(L) time and at most O(L) new nodes. Search costs O(number of trie states explored), at most O(T) for T stored nodes; a loose pattern-only upper bound is O(26^L). Search recursion uses O(L) stack space. Literal-only search is O(L).

Implementation notes (Go)

• Recursive search is straightforward because pattern lengths are typically moderate.
• A [26]*node child array avoids map allocation per lookup.

Reconstruction checkpoint

After adding "axe" and "box", evaluate ".ox", "..", and "b...". If the first wildcard branch is the a-child and fails, what must the search do next?

Return to Trie · Module quiz