Approach Summary
Trie with wildcard support. On '.' character during search, branch to all children.
Practice Mode
3 Progressive Approaches
Solve it yourself before revealing the code
DSA interviews test reasoning from brute force to optimal. Think through the constraints first.
Solution Progression (Brute Force → Most Optimized)
Understand the architectural evolution from naive baseline to optimal complexity.
| Approach | Time | Space | Core Strategy / Trade-off |
|---|---|---|---|
| 1 Approach 1: Trie with Backtracking DFS Wildcard Match (Optimal) | O(L) standard, O(26^d) for d dots | O(N * L) | Standard trie node with recursive search branching over 26 children on dot wildcards. |
| 2 Approach 2: Hash Map Grouped by Word Length (Baseline) | O(1) addWord, O(N * L) search | O(N * L) | Stores inserted words grouped by length in a hash map, comparing character by character with wildcard support. |
| 3 Approach 2: Hash Map Grouped by Word Length (Baseline) | O(1) addWord, O(N * L) search | O(N * L) | Stores inserted words grouped by length in a hash map, comparing character by character with wildcard support. |
Step 1: Baseline
Approach 1: Trie with Backtracking DFS Wildcard Match (Optimal)
Time: O(L) standard, O(26^d) for d dots
Space: O(N * L)
When searching, regular characters step into a single child. When hitting '.', iterate over all 26 possible branches, recursing on non-null children. If any branch succeeds, the search returns true.
Approach 1: Trie with Backtracking DFS Wildcard Match (Optimal) Implementation
Approach 1: Trie with Backtracking DFS Wildcard Match (Optimal)
class WordDictionary {
class Node { Node[] c = new Node[26]; boolean end; }
Node root = new Node();
public void addWord(String w) {
Node n = root;
for (char ch : w.toCharArray()) {
if (n.c[ch - 'a'] == null) n.c[ch - 'a'] = new Node();
n = n.c[ch - 'a'];
}
n.end = true;
}
public boolean search(String w) { return dfs(w, 0, root); }
private boolean dfs(String w, int idx, Node n) {
if (n == null) return false;
if (idx == w.length()) return n.end;
char ch = w.charAt(idx);
if (ch != '.') return dfs(w, idx + 1, n.c[ch - 'a']);
for (int i = 0; i < 26; i++) {
if (n.c[i] != null && dfs(w, idx + 1, n.c[i])) return true;
}
return false;
}
}class WordDictionary {
struct Node { Node* c[26] = {}; bool end = false; };
Node* root = new Node();
public:
void addWord(string w) {
Node* n = root;
for (char ch : w) {
if (!n->c[ch - 'a']) n->c[ch - 'a'] = new Node();
n = n->c[ch - 'a'];
}
n->end = true;
}
bool dfs(string& w, int idx, Node* n) {
if (!n) return false;
if (idx == w.size()) return n->end;
char ch = w[idx];
if (ch != '.') return dfs(w, idx + 1, n->c[ch - 'a']);
for (int i = 0; i < 26; i++) {
if (n->c[i] && dfs(w, idx + 1, n->c[i])) return true;
}
return false;
}
bool search(string w) { return dfs(w, 0, root); }
};class WordDictionary:
def __init__(self):
self.root = {}
def addWord(self, word: str):
n = self.root
for c in word:
n = n.setdefault(c, {})
n['$'] = True
def search(self, word: str) -> bool:
def dfs(i, n):
if i == len(word): return '$' in n
c = word[i]
if c != '.': return c in n and dfs(i + 1, n[c])
return any(dfs(i + 1, n[k]) for k in n if k != '$')
return dfs(0, self.root)class WordDictionary {
constructor() { this.root = {}; }
addWord(w) {
let n = this.root;
for (const c of w) { n[c] = n[c] || {}; n = n[c]; }
n.end = true;
}
search(w) {
const dfs = (i, n) => {
if (!n) return false;
if (i === w.length) return !!n.end;
const c = w[i];
if (c !== '.') return !!n[c] && dfs(i + 1, n[c]);
for (const k of Object.keys(n)) {
if (k !== 'end' && dfs(i + 1, n[k])) return true;
}
return false;
};
return dfs(0, this.root);
}
} Step 2
Approach 2: Hash Map Grouped by Word Length (Baseline)
Time: O(1) addWord, O(N * L) search
Space: O(N * L)
Groups words into buckets based on length. Searching word of length L only scans candidates in the corresponding length bucket, matching letters and allowing any character for dot wildcard.
Approach 2: Hash Map Grouped by Word Length (Baseline) Implementation
Approach 2: Hash Map Grouped by Word Length (Baseline)
class WordDictionary {
private Map<Integer, List<String>> map = new HashMap<>();
public void addWord(String word) {
map.computeIfAbsent(word.length(), k -> new ArrayList<>()).add(word);
}
public boolean search(String word) {
List<String> list = map.get(word.length());
if (list == null) return false;
for (String w : list) {
boolean ok = true;
for (int i = 0; i < word.length(); i++) {
if (word.charAt(i) != '.' && word.charAt(i) != w.charAt(i)) {
ok = false; break;
}
}
if (ok) return true;
}
return false;
}
}class WordDictionary {
unordered_map<int, vector<string>> map;
public:
void addWord(string word) {
map[word.size()].push_back(word);
}
bool search(string word) {
if (!map.count(word.size())) return false;
for (const string& w : map[word.size()]) {
bool ok = true;
for (int i = 0; i < word.size(); i++) {
if (word[i] != '.' && word[i] != w[i]) { ok = false; break; }
}
if (ok) return true;
}
return false;
}
};class WordDictionary:
def __init__(self):
self.words = collections.defaultdict(list)
def addWord(self, word: str) -> None:
self.words[len(word)].append(word)
def search(self, word: str) -> bool:
m = len(word)
for w in self.words[m]:
match = True
for i in range(m):
if word[i] != '.' and word[i] != w[i]:
match = False; break
if match: return True
return Falseclass WordDictionary {
constructor() { this.words = new Map(); }
addWord(word) {
const len = word.length;
if (!this.words.has(len)) this.words.set(len, []);
this.words.get(len).push(word);
}
search(word) {
const len = word.length;
if (!this.words.has(len)) return false;
for (const w of this.words.get(len)) {
let ok = true;
for (let i = 0; i < len; i++) {
if (word[i] !== '.' && word[i] !== w[i]) { ok = false; break; }
}
if (ok) return true;
}
return false;
}
} Step 2: Most Optimized
Approach 2: Hash Map Grouped by Word Length (Baseline)
Time: O(1) addWord, O(N * L) search
Space: O(N * L)
Groups words into buckets based on length. Searching word of length L only scans candidates in the corresponding length bucket, matching letters and allowing any character for dot wildcard.
Approach 2: Hash Map Grouped by Word Length (Baseline) Implementation
Approach 2: Hash Map Grouped by Word Length (Baseline)
class WordDictionary {
private Map<Integer, List<String>> map = new HashMap<>();
public void addWord(String word) {
map.computeIfAbsent(word.length(), k -> new ArrayList<>()).add(word);
}
public boolean search(String word) {
List<String> list = map.get(word.length());
if (list == null) return false;
for (String w : list) {
boolean ok = true;
for (int i = 0; i < word.length(); i++) {
if (word.charAt(i) != '.' && word.charAt(i) != w.charAt(i)) {
ok = false; break;
}
}
if (ok) return true;
}
return false;
}
}class WordDictionary {
unordered_map<int, vector<string>> map;
public:
void addWord(string word) {
map[word.size()].push_back(word);
}
bool search(string word) {
if (!map.count(word.size())) return false;
for (const string& w : map[word.size()]) {
bool ok = true;
for (int i = 0; i < word.size(); i++) {
if (word[i] != '.' && word[i] != w[i]) { ok = false; break; }
}
if (ok) return true;
}
return false;
}
};class WordDictionary:
def __init__(self):
self.words = collections.defaultdict(list)
def addWord(self, word: str) -> None:
self.words[len(word)].append(word)
def search(self, word: str) -> bool:
m = len(word)
for w in self.words[m]:
match = True
for i in range(m):
if word[i] != '.' and word[i] != w[i]:
match = False; break
if match: return True
return Falseclass WordDictionary {
constructor() { this.words = new Map(); }
addWord(word) {
const len = word.length;
if (!this.words.has(len)) this.words.set(len, []);
this.words.get(len).push(word);
}
search(word) {
const len = word.length;
if (!this.words.has(len)) return false;
for (const w of this.words.get(len)) {
let ok = true;
for (let i = 0; i < len; i++) {
if (word[i] !== '.' && word[i] !== w[i]) { ok = false; break; }
}
if (ok) return true;
}
return false;
}
}Edge Cases to Watch
- Search with only dots (e.g. "..." matches any 3-letter word)
- Search for word that is a prefix of a longer word without isEnd (returns false)
- Empty word or single character search
Algorithmic Pattern
View Pattern Guide →
Master the Trie Pattern
Study the core invariant, step-by-step decision framework, and common interview traps for the Trie pattern.
How to Recognize This Pattern
- Wildcard '.' in search
- Trie with DFS fallback
Complexity Analysis
Time Complexity
O(m) insert, O(26^m) worst search
Space Complexity
O(n × m)
Tags
Design Trie DFS Backtracking
Frequently Asked Questions
What is the optimal time and space complexity for Design Add and Search Words Data Structure?
The optimal solution for Design Add and Search Words Data Structure achieves O(m) insert, O(26^m) worst search runtime complexity and requires O(n × m) auxiliary space. Time complexity for addWord is O(L). For search: with no wildcards, it takes O(L). In the worst case with all wildcards "... ", it checks O(26^d) paths where d is the number of dots. Space complexity is O(N * L) for storing all words in the Trie.
How do I identify that Design Add and Search Words Data Structure requires the Trie pattern?
In technical interviews, look for key problem signals: Wildcard '.' in search; Trie with DFS fallback. Recognizing these invariants allows you to bypass naive brute-force exhaustive search in favor of Trie strategy.
What critical edge cases must be handled in Design Add and Search Words Data Structure?
Essential edge cases to verify include: Search with only dots (e.g. "..." matches any 3-letter word); Search for word that is a prefix of a longer word without isEnd (returns false); Empty word or single character search. Always walk through these scenarios with your interviewer before coding.
Which tech companies frequently ask Design Add and Search Words Data Structure?
Design Add and Search Words Data Structure is a Medium-difficulty question tagged with medium recurrence. It is actively asked in technical screening and onsite interview loops at Facebook, Bloomberg.