Design Add and Search Words Data Structure
The Prompt
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. `addWord(word)` adds `word` to the data structure. `search(word)` returns `true` if there is any string in the data structure that matches `word` or `false` otherwise. `word` may contain dots `.` where dots can be matched with any letter.
Understanding the Problem
This is a trie with one twist: search patterns may contain '.', which matches any single letter. addWord is a plain trie insert. A search with no dots is a plain trie walk. The dot is where the single path breaks down — you can no longer follow one child, because any child might lead to a match.
So a dot triggers a fan-out: recursively try every child of the current node against the rest of the pattern. That turns search into a DFS over the trie, where concrete letters keep the search narrow and dots temporarily widen it.
The Interview Flow
Interviewer
How would you build on the Trie structure to support wildcard searches, where `.` can match any character?
Candidate
The `addWord` function would be exactly the same as a standard Trie. The change comes in the `search` function.
Interviewer
How does the `search` function change?
Candidate
When I encounter a regular character, I traverse the trie as usual. However, when I encounter a `.` (dot), I can no longer follow a single path. I need to explore all possible paths from the current node.
Interviewer
How do you explore all paths?
Candidate
This requires a recursive (backtracking) search. My search function will take the current node in the trie and the current index in the word. If the character is a dot, I will iterate through all the children of the current node. For each child, I will make a recursive call to search for the rest of the word starting from that child node. If any of these recursive calls return true, then I have found a match.
Interviewer
What is the base case for this recursive search?
Candidate
The base case is when I have reached the end of the word. At that point, I check if the current node in the trie is marked as the end of a word. If it is, I return true.
Interviewer
This sounds like a correct and complete approach. The wildcard introduces a DFS/backtracking element into the standard trie traversal. Please implement it.
Why is DFS over the trie the right way to handle '.'?
The invariant of the recursion: a call at (node, i) returns true exactly when some stored word's suffix starting at this node matches pattern[i..]. A letter at position i preserves it by following one child; a dot preserves it by taking the OR over all children — together they cover every word that could match, and only those.
Cost: addWord is O(L). A dot-free search is O(L). Each dot multiplies the branching by up to 26, so a pattern of length L with d dots is O(26^d · L) in the worst case — bounded overall by the total size of the trie, since the DFS never leaves it.
Trie with Recursive Backtracking Search
- **1. `addWord`:** Implement this exactly like a standard Trie `insert` method.
- **2. `search`:** This will be a wrapper that calls a recursive helper.
- - **Recursive Helper `dfs(j, root)`:**
- - Takes `j` (current index in the word) and `root` (current node in the trie).
- - Loop from index `j` to the end of the word.
- - **If `word[i]` is NOT a dot:**
- - If the character is not in the current node's children, this path fails. Return `false`.
- - Move to the child node.
- - **If `word[i]` IS a dot:**
- - Iterate through all child nodes of the current node.
- - For each `child`, make a recursive call `dfs(i + 1, child)`.
- - If any of these calls return `true`, then a match is found. Return `true`.
- - If the loop finishes and no child path worked, this path fails. Return `false`.
- - After the loop (if no dots were handled), return `true` if the final node `isEndOfWord`.
- - Call the helper initially with `dfs(0, this.root)`.
Try it yourself
Write your solution and run it against 1 test cases.
JavaScript, TypeScript & Python run sandboxed in your browser; other languages run on the execution server. Your code is saved locally as you type.
Final Solution
class WordDictionary {
constructor() {
this.root = {};
}
addWord(word) {
let node = this.root;
for (const char of word) {
if (!node[char]) {
node[char] = {};
}
node = node[char];
}
node.isEnd = true;
}
search(word) {
function dfs(j, root) {
let curr = root;
for (let i = j; i < word.length; i++) {
const char = word[i];
if (char === '.') {
for (const key in curr) {
if (dfs(i + 1, curr[key])) {
return true;
}
}
return false;
} else {
if (!curr[char]) {
return false;
}
curr = curr[char];
}
}
return curr.isEnd === true;
}
return dfs(0, this.root);
}
}Explanation
Add "bad", "dad", and "mad", then search "pad" and ".ad".
1After addWord("bad"), addWord("dad"), addWord("mad"): three branches hang off the root — b, d, m — each continuing through a to a flagged d. Adding words never changes; it is a standard trie insert.
2search("pad"): 'p' is a concrete letter, so we look for a p child of the root. The root has only b, d, and m — the walk dies at the very first step and returns false.
3search(".ad"): the dot fans out to all three children of the root. The DFS tries the b branch first: b → a → d has the end flag, so it returns true immediately — the d and m branches never need exploring.
Complexity Analysis
TIME
O(L) for add, O(N*26^L) for search
SPACE
O(M)
Finished working through this one?
Mark it complete to track it on your Data Structures path.