Design Add and Search Words Data Structure (LeetCode 211)
Build a structure that can remember a growing set of words and later test whether a query string matches any of them.
Implement a WordDictionary class:
WordDictionary()starts with an empty set of words.void addWord(word)rememberswordso later searches can match it.bool search(word)returnstrueif some remembered word matchesword, elsefalse. Inword, a.character stands in for any single letter.
Worked Examples
["WordDictionary","addWord","addWord","addWord","search","search","search","search"]
[[],["bad"],["dad"],["mad"],["pad"],["bad"],[".ad"],["b.."]][null,null,null,null,false,true,true,true]"pad" was never added. "bad" was. ".ad" matches "bad", "dad" or "mad", and "b.." matches "bad".⚖️Formal Constraints & Bounds
1 <= word.length <= 25wordinaddWordconsists of lowercase English letters.wordinsearchconsist of'.'or lowercase English letters.There will be at most
2dots inwordforsearchqueries.At most
104calls will be made toaddWordandsearch.
Core Insight
A Trie with recursive branching evaluates wildcard queries in optimal prefix-constrained time.
Real-World Scenario & Production Applications
Regular expression matching engines, dictionary crossword wildcard lookups.
Step-by-Step Execution Trace Table
| Char in Query | Trie Action | Subtrees Explored | Match? |
|---|---|---|---|
| '.' | Branch across all children | 'b' and 'd' branches | - |
| 'a' | Follow 'a' child | 'ba' and 'da' | - |
| 'd' | Check terminal '$' | 'bad' () | True |
| 1 | def addWord(word): |
| 2 | insert word into the trie, as in a standard trie |
| 3 | def search(word): |
| 4 | def dfs(j, node): |
| 5 | for each character c of word from index j on: |
| 6 | if c == '.': |
| 7 | return True if dfs from the next index succeeds for any child |
| 8 | if c not in node: |
| 9 | return False |
| 10 | node = node[c] |
| 11 | return '$' in node |
Conceptual Narrative
Standard Trie search follows a single deterministic hallway per letter. The wildcard '.' transforms search into a non-deterministic parallel exploration of all 26 branches simultaneously.
🧭 Conceptual Foundation & Pattern Intuition
In a standard Trie, each character corresponds to at most one child node ( descent). In WordDictionary (LC 211), the query pattern may contain wildcards '.', where '.' matches any lowercase English letter.
When the search encounters a literal character ('a'-'z'), it executes standard deterministic descent. When it encounters '.', determinism breaks: the algorithm must branch into a recursive DFS across all currently allocated child nodes at that level. If any child path returns True, the search immediately short-circuits and returns True.
Worst-case complexity for a word of all dots "..." is in a dense Trie, but real-world dictionaries are sparse: words diverge, dead ends abort instantly, and search depth is strictly bounded by word length .
🗝️ The Analogy: The Skeleton Key in a Corridor of 26 Doors
Imagine searching an office building for a specific employee. A literal letter 'b' means you must open the door labeled 'b'. But a wildcard '.' is a skeleton key that can open any door in the hallway. When you hold a skeleton key, you continue the search behind every door in the corridor, one door after another. As soon as the search behind one door finds the employee, you stop searching.
🔑 Why It Works
By splicing the string slice word[i + 1:] or passing an index pointer idx, literal characters cost descent while wildcards branch only across instantiated children, achieving optimal performance on sparse prefix trees.
Wildcard dot exponential branching without pruning: Branching into all 26 children on
.without early pruning when no child nodes exist.Overwriting
is_endboolean on duplicate adds: Adding a word that already exists should preserveis_end = True.Linear search fallback: Falling back to linear scan across all inserted words instead of recursive DFS down the Trie on wildcard
.characters.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
Prefix tree search with single-character wildcard '.' matching.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Invariant: wildcard '.' explores all existing child branches recursively.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
Iterative search without stack on wildcard: '.' requires backtracking across multiple children.
Checking terminal '$' on intermediate non-word nodes.
The 60-Second Interview Pitch
Say this out loud before you type a single line
"I build a standard Trie using nested dictionaries. For
search(word), I use helperdfs(j, node). Ifword[i] == '.', I recursively explore all child nodes innode.values(). Otherwise, I follow the exact character branch. At the end, I check if$is in the terminal node. Runs in O(L) for normal search and O(26^L) worst-case wildcard time."
Complexity & Mathematical Proof
O(L) Add, O(26^D · L) Search
Look at the execution steps: Adding word of length L takes O(L). Searching without dots takes O(L); wildcard '.' branches across at most 26 children (at depth D with D dots, takes O(26^D * L)).
O(N · L · |Sigma|) Auxiliary
Look at memory allocations: Call stack uses O(L) Recursion depth during search. Trie storage holding N words of length L.
Tadd = O(L), Tsearch = O(26^D · L)
Derivation Progression
O(1) child lookup
Follows exact character edge in constant time.
26 recursive child searches
Recursively explores all 26 non-null child nodes for '.' wildcard.
O(26^D · L) where D = number of dots
Worst case when word consists entirely of '.' wildcards.
Variable Definitions
Length of the word or query
Number of wildcard '.' dots in search pattern
Memory Architecture & Bounds
O(L) Recursion depth during search
O(N · L · |Sigma|) TrieNode tree
O(1) Boolean return
Boundary Best / Worst Cases
when search has no wildcards.
.
for string of all '.' wildcards.
Recurrence Tree Topology
Senior SWE Deconstruction & Hardware Caveats
Triggers: "addWord", "search words with '.' matching any letter". Literal characters traverse a single Trie child, while the wildcard character '.' branches across all existing children. A Senior SWE applies Trie + Recursive Wildcard DFS Backtracking.
Word length , at most 2 dots per search query, up to operations. At most operations in the worst case.
Base case termination: when , return node.is_end. If the child path doesn't exist, return False immediately without unneeded calls.
Design Add and Search Words Data Structure (LeetCode 211)
Build a structure that can remember a growing set of words and later test whether a query string matches any of them.
Implement a WordDictionary class:
WordDictionary()starts with an empty set of words.void addWord(word)rememberswordso later searches can match it.bool search(word)returnstrueif some remembered word matchesword, elsefalse. Inword, a.character stands in for any single letter.
Worked Examples
["WordDictionary","addWord","addWord","addWord","search","search","search","search"]
[[],["bad"],["dad"],["mad"],["pad"],["bad"],[".ad"],["b.."]][null,null,null,null,false,true,true,true]"pad" was never added. "bad" was. ".ad" matches "bad", "dad" or "mad", and "b.." matches "bad".⚖️Formal Constraints & Bounds
1 <= word.length <= 25wordinaddWordconsists of lowercase English letters.wordinsearchconsist of'.'or lowercase English letters.There will be at most
2dots inwordforsearchqueries.At most
104calls will be made toaddWordandsearch.
Core Insight
A Trie with recursive branching evaluates wildcard queries in optimal prefix-constrained time.
Real-World Scenario & Production Applications
Regular expression matching engines, dictionary crossword wildcard lookups.
Step-by-Step Execution Trace Table
| Char in Query | Trie Action | Subtrees Explored | Match? |
|---|---|---|---|
| '.' | Branch across all children | 'b' and 'd' branches | - |
| 'a' | Follow 'a' child | 'ba' and 'da' | - |
| 'd' | Check terminal '$' | 'bad' () | True |
| 1 | def addWord(word): |
| 2 | insert word into the trie, as in a standard trie |
| 3 | def search(word): |
| 4 | def dfs(j, node): |
| 5 | for each character c of word from index j on: |
| 6 | if c == '.': |
| 7 | return True if dfs from the next index succeeds for any child |
| 8 | if c not in node: |
| 9 | return False |
| 10 | node = node[c] |
| 11 | return '$' in node |
Conceptual Narrative
Standard Trie search follows a single deterministic hallway per letter. The wildcard '.' transforms search into a non-deterministic parallel exploration of all 26 branches simultaneously.
🧭 Conceptual Foundation & Pattern Intuition
In a standard Trie, each character corresponds to at most one child node ( descent). In WordDictionary (LC 211), the query pattern may contain wildcards '.', where '.' matches any lowercase English letter.
When the search encounters a literal character ('a'-'z'), it executes standard deterministic descent. When it encounters '.', determinism breaks: the algorithm must branch into a recursive DFS across all currently allocated child nodes at that level. If any child path returns True, the search immediately short-circuits and returns True.
Worst-case complexity for a word of all dots "..." is in a dense Trie, but real-world dictionaries are sparse: words diverge, dead ends abort instantly, and search depth is strictly bounded by word length .
🗝️ The Analogy: The Skeleton Key in a Corridor of 26 Doors
Imagine searching an office building for a specific employee. A literal letter 'b' means you must open the door labeled 'b'. But a wildcard '.' is a skeleton key that can open any door in the hallway. When you hold a skeleton key, you continue the search behind every door in the corridor, one door after another. As soon as the search behind one door finds the employee, you stop searching.
🔑 Why It Works
By splicing the string slice word[i + 1:] or passing an index pointer idx, literal characters cost descent while wildcards branch only across instantiated children, achieving optimal performance on sparse prefix trees.
Wildcard dot exponential branching without pruning: Branching into all 26 children on
.without early pruning when no child nodes exist.Overwriting
is_endboolean on duplicate adds: Adding a word that already exists should preserveis_end = True.Linear search fallback: Falling back to linear scan across all inserted words instead of recursive DFS down the Trie on wildcard
.characters.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
Prefix tree search with single-character wildcard '.' matching.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Invariant: wildcard '.' explores all existing child branches recursively.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
Iterative search without stack on wildcard: '.' requires backtracking across multiple children.
Checking terminal '$' on intermediate non-word nodes.
The 60-Second Interview Pitch
Say this out loud before you type a single line
"I build a standard Trie using nested dictionaries. For
search(word), I use helperdfs(j, node). Ifword[i] == '.', I recursively explore all child nodes innode.values(). Otherwise, I follow the exact character branch. At the end, I check if$is in the terminal node. Runs in O(L) for normal search and O(26^L) worst-case wildcard time."
Complexity & Mathematical Proof
O(L) Add, O(26^D · L) Search
Look at the execution steps: Adding word of length L takes O(L). Searching without dots takes O(L); wildcard '.' branches across at most 26 children (at depth D with D dots, takes O(26^D * L)).
O(N · L · |Sigma|) Auxiliary
Look at memory allocations: Call stack uses O(L) Recursion depth during search. Trie storage holding N words of length L.
Tadd = O(L), Tsearch = O(26^D · L)
Derivation Progression
O(1) child lookup
Follows exact character edge in constant time.
26 recursive child searches
Recursively explores all 26 non-null child nodes for '.' wildcard.
O(26^D · L) where D = number of dots
Worst case when word consists entirely of '.' wildcards.
Variable Definitions
Length of the word or query
Number of wildcard '.' dots in search pattern
Memory Architecture & Bounds
O(L) Recursion depth during search
O(N · L · |Sigma|) TrieNode tree
O(1) Boolean return
Boundary Best / Worst Cases
when search has no wildcards.
.
for string of all '.' wildcards.
Recurrence Tree Topology
Senior SWE Deconstruction & Hardware Caveats
Triggers: "addWord", "search words with '.' matching any letter". Literal characters traverse a single Trie child, while the wildcard character '.' branches across all existing children. A Senior SWE applies Trie + Recursive Wildcard DFS Backtracking.
Word length , at most 2 dots per search query, up to operations. At most operations in the worst case.
Base case termination: when , return node.is_end. If the child path doesn't exist, return False immediately without unneeded calls.