47 / 75
Medium
Design Add and Search Words Data Structure
#47triedfsbacktrackingstringdesign
Implement Trie with wildcard search using DFS to try all branches when '.' encountered.
Example:
Input:
addWord('bad'), addWord('dad'), search('.ad'), search('b..')Output:
true, true (both patterns match)Common Mistakes:
- Not using DFS/backtracking for wildcard handling
- Trying to handle '.' iteratively (much harder)
- Not checking null nodes before recursing
- Forgetting to check isEnd when reaching word end
Notes:
Extends Trie with backtracking. addWord: O(m), search: O(m) best case, O(26^m) worst case with all dots. Space O(total chars).
💻
Java Solution Hidden
Enable “Show Full Solution” to view the code
Implement Trie with wildcard search using DFS to try all branches when '.' encountered.
Example:
Input:
addWord('bad'), addWord('dad'), search('.ad'), search('b..')Output:
true, true (both patterns match)Common Mistakes:
- Not using DFS/backtracking for wildcard handling
- Trying to handle '.' iteratively (much harder)
- Not checking null nodes before recursing
- Forgetting to check isEnd when reaching word end
Notes:
Extends Trie with backtracking. addWord: O(m), search: O(m) best case, O(26^m) worst case with all dots. Space O(total chars).
47/75
Design Add and Search Words Data Structure