Design Add and Search Words Data Structure
Asked at Amazon, Meta, Microsoft, Atlassian
Difficulty
Medium
Time
addWord: O(m). search: O(26^d *
Space
O(26 * m * n) for the trie, wher
Pattern
String
Companies
4
Problem
Design a class called WordDictionary that stores words and can later check whether a stored word matches a given pattern.
addWord(word) inserts a word so it can be matched later. search(word) returns true if any stored word matches the pattern, and false otherwise. The pattern looks like a normal word, except it may contain the character . (a dot). A dot is a wildcard: it matches exactly one letter, any letter. So the pattern b.. matches any stored word of length 3 that starts with b.
A match must use the whole pattern and the whole stored word — same length, every position matching. The dot does not match zero letters and does not match more than one letter.
A dot matches any one letter
Constraints
- ●
1 <= word.length <= 25 - ●
word in addWord consists of lowercase English letters only - ●
word in search consists of '.' or lowercase English letters - ●
There are at most 2 dots in any search word - ●
At most 10^4 total calls are made to addWord and search
Examples
["WordDictionary","addWord","addWord","addWord","search","search","search","search"]
[[],["bad"],["dad"],["mad"],["pad"],["bad"],[".ad"],["b.."]][null,null,null,null,false,true,true,true]["WordDictionary","addWord","search","search"]
[[],["a"],["a"],["."]][null,null,true,true]["WordDictionary","addWord","search","search"]
[[],["abc"],["ab"],["abcd"]][null,null,false,false]Asked At
4 companies| 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.
Trie plus DFS at the dots
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
addWord: O(m). search: O(26^d * timeclass 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 runs in addWord: O(m). search: O(26^d * time and O(26 * m * n) for the trie, wher space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.
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.