162. Design Add and Search Words Data Structure
🔗 LeetCode Problem: 211. Design Add and Search Words Data Structure
📊 Difficulty: Medium
🏷️ Topics: Trie, String, DFS, Backtracking, Design
Problem Statement
Design a data structure that supports adding new words and finding if a string matches any previously added string.
Implement the WordDictionary class:
WordDictionary()Initializes the object.void addWord(word)Addswordto the data structure, it can be matched later.bool search(word)Returnstrueif there is any string in the data structure that matcheswordorfalseotherwise.wordmay contain dots'.'where dots can be matched with any letter.
Example:
Input
["WordDictionary","addWord","addWord","addWord","search","search","search","search"]
[[],["bad"],["dad"],["mad"],["pad"],["bad"],[".ad"],["b.."]]
Output
[null,null,null,null,false,true,true,true]
Explanation
WordDictionary wordDictionary = new WordDictionary();
wordDictionary.addWord("bad");
wordDictionary.addWord("dad");
wordDictionary.addWord("mad");
wordDictionary.search("pad"); // return False
wordDictionary.search("bad"); // return True
wordDictionary.search(".ad"); // return True (matches "bad", "dad", "mad")
wordDictionary.search("b.."); // return True (matches "bad")
Constraints:
- 1 <= word.length <= 25
- word in addWord consists of lowercase English letters
- word in search consist of '.' or lowercase English letters
- There will be at most 2 dots in word for search queries
- At most 10^4 calls will be made to addWord and search
🌳 Visual Understanding - The Wildcard Challenge
Building on Problem 161:
PROBLEM 161 (Basic Trie):
addWord("bad")
search("bad") → true
search("dad") → false
PROBLEM 162 (Wildcard Trie):
addWord("bad")
addWord("dad")
addWord("mad")
search(".ad") → true (matches all three!)
search("b..") → true (matches "bad")
NEW CHALLENGE: Handle '.' wildcard! 🎯
The Wildcard Problem:
Trie after adding ["bad", "dad", "mad"]:
root
/ | \
b d m
| | |
a a a
| | |
d* d* d*
Search "bad":
b → a → d (exact match) ✓
Search ".ad":
. → must try ALL children at this level!
↓
b, d, m (try all three)
↓
a, a, a (continue for each)
↓
d, d, d (check end)
Any path reaches end? YES! → true ✓
Need to explore MULTIPLE PATHS! 🔑
Key Insight:
Without wildcard ('.'):
- Single deterministic path
- Follow exact characters
- O(m) time
With wildcard ('.'):
- Multiple possible paths
- Try ALL children at wildcard position
- Need DFS/Backtracking!
- O(26^k * m) worst case (k = wildcards)
This changes everything! 🎯
🧠 The AHA Moment - DFS for Wildcards
The Algorithm:
Regular character ('a'-'z'):
- Follow that specific child
- Like Problem 161
Wildcard character ('.'):
- Try ALL 26 children!
- Use DFS/recursion
- Return true if ANY path succeeds
Example: search(".ad")
At root, see '.':
Try child[0] (a) → a-a-d? No
Try child[1] (b) → b-a-d? Yes! ✓
Found one → return true
Don't need to try all if one succeeds! ✨
Recursive Strategy:
search(word, index, node):
Base case:
if index == word.length:
return node.isEndOfWord
Current char = word[index]
if char == '.':
// Try all 26 children
for i in 0..25:
if node.children[i] != null:
if search(word, index+1, node.children[i]):
return true // Found a match!
return false // No path worked
else:
// Regular character
child = node.children[char - 'a']
if child == null:
return false
return search(word, index+1, child)
🎯 Solution: Trie + DFS
Complete Implementation:
class WordDictionary {
private class TrieNode {
TrieNode[] children = new TrieNode[26];
boolean isEndOfWord = false;
}
private TrieNode root;
public WordDictionary() {
root = new TrieNode();
}
public void addWord(String word) {
// Same as Problem 161!
TrieNode node = root;
for (char c : word.toCharArray()) {
int i = c - 'a';
if (node.children[i] == null) {
node.children[i] = new TrieNode();
}
node = node.children[i];
}
node.isEndOfWord = true;
}
public boolean search(String word) {
// Start DFS from root at index 0
return searchDFS(word, 0, root);
}
private boolean searchDFS(String word, int index, TrieNode node) {
// Base case: reached end of word
if (index == word.length()) {
return node.isEndOfWord;
}
char ch = word.charAt(index);
if (ch == '.') {
// Wildcard: try all 26 children
for (int i = 0; i < 26; i++) {
if (node.children[i] != null) {
// Recursively search from this child
if (searchDFS(word, index + 1, node.children[i])) {
return true; // Found a match!
}
}
}
// None of the paths worked
return false;
} else {
// Regular character: follow specific path
int i = ch - 'a';
if (node.children[i] == null) {
return false; // Path doesn't exist
}
return searchDFS(word, index + 1, node.children[i]);
}
}
}
🔍 Detailed Dry Run - Wildcard Search
Trie state after:
addWord("bad")
addWord("dad")
addWord("mad")
root
/ | \
b d m
| | |
a a a
| | |
d* d* d*
Search ".ad"
═══════════════════════════════════════════════════
SEARCH ".ad" - DFS EXPLORATION
═══════════════════════════════════════════════════
CALL 1: searchDFS(".ad", 0, root)
────────────────────────────────────────────────────
├─ index = 0
├─ ch = '.' ← WILDCARD!
├─ Try all 26 children of root
│
├─ children[0] (a): null, skip
├─ children[1] (b): exists!
│ └─ RECURSIVE: searchDFS(".ad", 1, node_b) ──┐
│ │
│ CALL 2: searchDFS(".ad", 1, node_b) │
│ ───────────────────────────────────── │
│ ├─ index = 1 │
│ ├─ ch = 'a' │
│ ├─ Follow child[0] (a): exists │
│ └─ RECURSIVE: searchDFS(".ad", 2, node_ba) ──┤
│ │
│ CALL 3: searchDFS(".ad", 2, node_ba) │
│ ───────────────────────────────── │
│ ├─ index = 2 │
│ ├─ ch = 'd' │
│ ├─ Follow child[3] (d): exists │
│ └─ RECURSIVE: searchDFS(".ad", 3, node_bad)│
│ │
│ CALL 4: searchDFS(".ad", 3, node_bad) │
│ ───────────────────────────────── │
│ ├─ index = 3 == word.length ✓ │
│ ├─ BASE CASE! │
│ ├─ isEndOfWord? true ✓ │
│ └─ return true │
│ │
│ ← return true (from CALL 3) │
│ ← return true (from CALL 2) │
└─ FOUND MATCH! Return true immediately │
Result: true (matched "bad") ✓
Note: Didn't need to try 'd' or 'm'!
Early termination on first match! ⚡
═══════════════════════════════════════════════════
Search "b.."
═══════════════════════════════════════════════════
SEARCH "b.." - MULTIPLE WILDCARDS
═══════════════════════════════════════════════════
CALL 1: searchDFS("b..", 0, root)
────────────────────────────────────────────────────
├─ ch = 'b' (regular)
├─ Follow child[1]: exists
└─ RECURSIVE: searchDFS("b..", 1, node_b)
CALL 2: searchDFS("b..", 1, node_b)
────────────────────────────────────────────────────
├─ ch = '.' (first wildcard!)
├─ Try all children of node_b
│
├─ child[0] (a): exists
│ └─ RECURSIVE: searchDFS("b..", 2, node_ba)
│
│ CALL 3: searchDFS("b..", 2, node_ba)
│ ────────────────────────────────────
│ ├─ ch = '.' (second wildcard!)
│ ├─ Try all children of node_ba
│ │
│ ├─ child[3] (d): exists
│ │ └─ RECURSIVE: searchDFS("b..", 3, node_bad)
│ │
│ │ CALL 4: searchDFS("b..", 3, node_bad)
│ │ ────────────────────────────────────
│ │ ├─ index = 3 == length ✓
│ │ ├─ isEndOfWord? true ✓
│ │ └─ return true
│ │
│ └─ return true
│
└─ return true
Result: true (matched "bad") ✓
Path taken: b → . (try a) → . (try d) → found! ✨
═══════════════════════════════════════════════════
Search "pad" (No Match)
═══════════════════════════════════════════════════
SEARCH "pad" - FAIL CASE
═══════════════════════════════════════════════════
CALL 1: searchDFS("pad", 0, root)
────────────────────────────────────────────────────
├─ ch = 'p'
├─ child[15] (p): null ✗
└─ return false
Result: false (no word starts with 'p') ✗
Fast failure! No DFS needed! ⚡
═══════════════════════════════════════════════════
📊 Complexity Analysis
addWord(word):
Time: O(m) where m = word length
- Same as Problem 161
- No change!
Space: O(m) for new nodes in worst case
search(word) - The Interesting Part:
WITHOUT wildcards:
Time: O(m)
- Follow single path
- Same as Problem 161
WITH wildcards:
Time: O(26^k * m) worst case
where k = number of wildcards
Why?
- Each wildcard: try up to 26 children
- If k wildcards: 26^k possible paths
- Each path: O(m) to traverse
Example: search("...")
- 3 wildcards
- 26^3 = 17,576 possible paths! 😱
- But: constraint says max 2 wildcards
- So: O(26^2 * m) = O(676 * m) max
Space: O(m) for recursion depth
- Call stack depth = word length
Best vs Worst Case:
BEST CASE: search("abc")
- No wildcards
- O(m) time
- Single path
WORST CASE: search("...")
- All wildcards
- O(26^3 * m) time
- Explore all possible 3-character words!
AVERAGE CASE: search(".ad")
- One wildcard
- O(26 * m) time
- Try 26 paths at wildcard position
Why DFS is Necessary:
Can't use simple iteration!
Example: search(".ad")
Need to check:
aad, bad, cad, dad, ..., zad
Can't know which exists without trying!
Must explore all possibilities!
DFS/Recursion is REQUIRED! 🔑
🎯 Pattern Recognition - Trie + DFS
Core Pattern: Trie + Backtracking
When you see:
✓ Trie structure
✓ Wildcard/pattern matching
✓ Multiple possible paths
Think: Trie + DFS!
Template:
boolean searchWithWildcard(String word, int index, TrieNode node) {
if (index == word.length()) {
return node.isEnd;
}
char ch = word.charAt(index);
if (ch == WILDCARD) {
for (TrieNode child : node.children) {
if (child != null && searchWithWildcard(word, index+1, child)) {
return true;
}
}
return false;
} else {
// Regular character
return child exists && searchWithWildcard(word, index+1, child);
}
}
Related Problems:
1. Word Search II (212) - Hard
Trie + 2D Grid DFS
- Build trie of words
- DFS on grid using trie for pruning
- Backtracking on both grid and trie
2. Regular Expression Matching (10) - Hard
Similar wildcard concept
- '.' matches any single character
- '*' matches zero or more
- Need DP or recursion
3. Wildcard Matching (44) - Hard
Pattern matching with wildcards
- '?' matches single character
- '*' matches sequence
- Similar DFS approach
When to Use This Pattern:
✓ Trie + pattern matching
✓ Multiple possible matches
✓ Wildcards/special characters
✓ Need to explore alternatives
✓ Backtracking required
Not needed when:
✗ Exact string matching only
✗ No wildcards
✗ Single deterministic path
🆚 Comparison: Problem 161 vs 162
┌─────────────────────────────────────────────────┐
│ PROBLEM 161 vs 162 │
├─────────────────┬───────────────────────────────┤
│ Feature │ 161 │ 162 │
├─────────────────┼────────────┼──────────────────┤
│ Insert │ O(m) │ O(m) │
│ Search (exact) │ O(m) │ O(m) │
│ Search (wild) │ N/A │ O(26^k * m) │
│ Algorithm │ Iteration │ DFS/Recursion │
│ Complexity │ Simple │ Medium │
│ Key Difference │ One path │ Multiple paths │
└─────────────────┴────────────┴──────────────────┘
Problem 162 = Problem 161 + DFS for wildcards! 🎯
📝 Quick Revision Notes
🎯 Core Concept
Problem 162 adds wildcard support to basic Trie (Problem 161). When search encounters '.' wildcard, must try ALL 26 children using DFS/recursion. Regular characters follow single path (O(m)), wildcards explore multiple paths (O(26^k * m) where k = wildcard count). Early termination: return true on first match. addWord identical to Problem 161.
⚡ Quick Implementation
class TrieNode {
TrieNode[] children;
boolean isEnd;
public TrieNode() {
// Just space allocated. All are NULLs.
// For example, this.children[0] = null, this.children[1] = null and so on till this.children[25] = null
// Why null? We will initialize with new TrieNode() only when character comes. Why unncessary space before char comes?
// Check insert method. Only when character comes, we go and initialize that element in the array.
this.children = new TrieNode[26];
this.isEnd = false;
}
}
class WordDictionary {
TrieNode root;
public WordDictionary() {
root = new TrieNode();
}
public void addWord(String word) {
// Get the current root of the tree.
TrieNode curr = root;
for(char ch : word.toCharArray()) {
int index = ch - 'a';
if(curr.children[index] == null) {
curr.children[index] = new TrieNode(); // when you initialize, it is non-null and it means character is present.
}
// now move to next char
curr = curr.children[index];
}
// marks the end of the word. Useful to find whether the full word is present there or not instead of pattern/prefix.
curr.isEnd = true;
}
public boolean search(String word) {
// start or match character at index 0.
return dfs(word, 0, root);
}
private boolean dfs(String word, int i, TrieNode root) {
if(i == word.length()) {
return root.isEnd; // reached last character of the word
}
char ch = word.charAt(i);
// 2 cases: . and a proper character.
if(ch == '.') {
// we have to search for all 26 characters because of . as it can match for any next char.
// If we have ["bad", "dad"] in dict and search for ".ad", we need to match all words in dict.
for(int j = 0; j < 26; j++) {
// assuming b for first time and d for next time like that, match all chars.
// Before making DFS call, check if that char present in Trie. For example, 'c' is not present
// in above dict and moving forward is waste.
if(root.children[j] == null) {
continue;
}
if(dfs(word, i + 1, root.children[j])) {
return true;
}
}
return false;
} else {
int index = ch - 'a';
// check if char present at this index. Or do a match.
if(root.children[index] == null) {
return false;
}
root = root.children[index];
// continue search for next character.
return dfs(word, i + 1, root);
}
}
}
public class Solution {
public static void main(String[] args) {
WordDictionary wd = new WordDictionary();
wd.addWord("bad");
wd.addWord("dad");
wd.addWord("mad");
System.out.println(wd.search("pad")); // false
System.out.println(wd.search("bad")); // true
System.out.println(wd.search(".ad")); // true
System.out.println(wd.search("b..")); // true
}
}
🔑 Key Insights
Wildcard = Branch Point:
Regular char: ─→ (one path)
Wildcard '.': ─┬─→ a
├─→ b
├─→ c
└─→ ... (26 branches!)
DFS explores all branches! 🌳
Early Termination:
for (child : children) {
if (child != null && dfs(...)) {
return true; // Stop on first match!
}
}
Don't need to try all if one succeeds! ⚡
Recursion Stack:
Word length = recursion depth
3-char word = max 3 recursive calls
Space: O(m) for call stack
Not exponential space! Just time! 🔑
🎪 Memory Aid
"Wildcard? Try ALL children!"
"Regular char? One path only!"
"DFS returns true? Done!"
"Problem 161 + DFS = Problem 162!" ✨
⚠️ Don't Forget
- Wildcard needs loop (all 26 children!)
- Return true on first match (early termination!)
- Regular char = single path (no loop!)
- Base case: index == length (check isEnd!)
- DFS parameter: (word, index, node) - all three!
🎉 Congratulations!
You've mastered Trie with wildcards - combining data structures with search algorithms!
What You Learned:
✅ Wildcard handling - DFS for multiple paths
✅ Backtracking - Explore alternatives
✅ Early termination - Stop on first match
✅ Recursion depth - Word length stack
✅ Complexity analysis - Exponential vs linear
✅ Pattern recognition - Trie + DFS combo
The Key Difference:
Problem 161: Trie with exact matching
- Iterative
- Single path
- O(m)
Problem 162: Trie with wildcard matching
- Recursive (DFS)
- Multiple paths
- O(26^k * m)
Same structure, different search! 🎯
Interview Mastery:
Interviewer: "Add wildcard support to Trie"
Your response:
"Building on basic Trie (Problem 208).
Key change: search() method
Regular character:
- Follow specific child (index = ch - 'a')
- Single deterministic path
Wildcard '.':
- Try ALL 26 children
- Use DFS/recursion
- Return true if ANY path matches
Implementation:
- Recursive helper: dfs(word, index, node)
- Base case: index == length, check isEnd
- Wildcard case: loop all children
- Regular case: follow one child
Complexity:
- Without wildcards: O(m)
- With k wildcards: O(26^k * m)
- Problem limits to 2 wildcards: O(676*m)
Early termination on first match
keeps average case better than worst case."
Shows complete understanding! 💯
You've now mastered Trie + DFS - a powerful combination! 🏆✨🎯