Design Add and Search Words Data Structure
Asked at Amazon, Meta, Microsoft, Atlassian
Problem
Design a data structure that supports adding words and searching for words, where the search word may contain dots (a period character) that can match any letter. This is a Trie design problem with a twist — the wildcard character makes search require DFS instead of simple traversal.
Asked At
| Company | Difficulty | |
|---|---|---|
| Amazon | Medium | View all Amazon questions → |
| Meta | Medium | View all Meta questions → |
| Microsoft | Medium | View all Microsoft questions → |
| Atlassian | Medium | View all Atlassian questions → |
How to Think About It
Data structure: use a Trie (prefix tree). Each node has a map of children (char → node) and a boolean isEnd marking complete words. Add is standard Trie insertion — O(m) where m is word length.
Search with wildcards: when you hit a regular character, follow the corresponding child. When you hit a dot (.), you must try ALL children recursively. This is DFS — branch out at dots, backtrack if a branch fails.
Why DFS works: a dot can match any letter, so you explore all possible continuations. If any branch leads to a match, the search succeeds. If all branches fail, the word is not found.
Complexity: Add is O(m). Search is O(26^d × m) worst case where d is the number of dots, but in practice the Trie prunes branches early. For most real inputs, it is much faster than the worst case.
Edge cases: empty word (should match only if a word was added as empty string), dot at the start, consecutive dots, word longer than any stored prefix (early termination via null child).
Optimal Approach
TrieNode: map of children + isEnd flag.
Add: start at root, for each character create child if missing, move to child, mark last node as isEnd.
Search: recursive DFS. Base cases: if word is empty, return isEnd of current node. If current char is dot, try ALL children — if any recursive call returns true, return true. If current char is regular, follow that child (return false if null). Recurse on remaining word.
Time: Add O(m). Search O(26^m) worst case, O(m) best case (no dots). Space: O(ALPHABET_SIZE × m × n) for the Trie.
What Trips People Up in Real Interviews
Trying to replace dots with all letters and search — this creates 26^n combinations and blows up exponentially. DFS with early termination is the correct approach.
Forgetting to mark isEnd nodes. Without this, you cannot distinguish between a prefix and a complete word.
Not pruning the DFS. When a child is null, don't recurse — that branch has no words.
Using a HashMap for children instead of a fixed 26-element array. Both work, but HashMap uses more memory per node. For interviews, either is acceptable — just be consistent.
Solution Code
class TrieNode:
def __init__(self):
self.children = {}
self.is_end = False
class WordDictionary:
def __init__(self):
self.root = TrieNode()
def addWord(self, word):
node = self.root
for c in word:
if c not in node.children:
node.children[c] = TrieNode()
node = node.children[c]
node.is_end = True
def search(self, word):
def dfs(node, i):
if i == len(word):
return node.is_end
if word[i] == '.':
for child in node.children.values():
if dfs(child, i + 1):
return True
return False
if word[i] not in node.children:
return False
return dfs(node.children[word[i]], i + 1)
return dfs(self.root, 0)Frequently Asked Questions
What is the Design Add and Search Words Data Structure problem?
Design a data structure that supports adding words and searching for words, where the search word may contain dots (a period character) that can match any letter. This is a Trie design problem with a twist — the wildcard character makes search require DFS instead of simple traversal.
How do you solve Design Add and Search Words Data Structure?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Design Add and Search Words Data Structure?
Design Add and Search Words Data Structure is asked at Amazon, Meta, Microsoft, Atlassian. It is a medium difficulty problem.
What are common mistakes on Design Add and Search Words Data Structure?
- Trying to replace dots with all letters and search — this creates 26^n combinations and blows up exponentially. DFS with early termination is the correct approach.
- Forgetting to mark `isEnd` nodes. Without this, you cannot distinguish between a prefix and a complete word.
- Not pruning the DFS. When a child is null, don't recurse — that branch has no words.
- Using a HashMap for children instead of a fixed 26-element array. Both work, but HashMap uses more memory per node. For interviews, either is acceptable — just be consistent.