Design Add and Search Words Data Structure
Asked at Google, Meta, Amazon, Microsoft and 1 more
Difficulty
Medium
Time
addWord: O(m), where m is the wo
Space
O(total characters stored) for t
Pattern
Trie
Companies
5
Problem
Design a class that stores words and can later answer match queries against them.
You need two methods. addWord(word) stores a word so it can be matched later. search(word) returns true if any stored word matches the query exactly, otherwise false. The query may contain the special character ., and each . matches any single letter.
A query only matches a word of the same length. For example, after adding "bad", the query "b.." matches, but "b." does not, because the lengths differ. The same word may be added more than once; that changes nothing.
Dots match any one letter
Constraints
- ●
1 <= word.length <= 25 for both addWord and search - ●
word in addWord consists of lowercase English letters only - ●
word in search consists of lowercase English letters and '.' - ●
At most 10^4 calls are made in total 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"],["a."]][null,null,true,false]["WordDictionary","addWord","search","search"]
[[],["abc"],["..."],["...."]][null,null,true,false]Asked At
5 companies| Company | Difficulty | |
|---|---|---|
| Medium | View all Google questions → | |
| Meta | Medium | View all Meta questions → |
| Amazon | Medium | View all Amazon questions → |
| Microsoft | Medium | View all Microsoft questions → |
| Apple | Medium | View all Apple questions → |
How to Think About It
This is a trie with a twist: the search method needs to handle wildcard dots.
Insert is standard trie insertion — nothing changes.
Search with wildcards: use DFS. At each dot, try all 26 children recursively. If any branch returns true, the word exists.
On a regular character, follow that child. If missing, return false immediately. No need to explore other branches.
Why DFS works: a dot branches into up to 26 recursive calls. In the worst case (all dots), you explore 26^m paths. But most searches have no dots, so it's O(m) like a normal trie.
Edge cases: empty word, all dots, word longer than any stored word, word shorter than stored words.
Optimal Approach
class TrieNode:
children = {}
is_end = False
addWord(word): standard trie insertion.
search(word): DFS at root. At index i:
If i == len(word), return node.is_end.
If char is '.', try all children recursively. If any returns true, return true.
If char is specific, follow that child (or return false if missing).
Time: O(m) for addWord. O(26^m) worst case for search with dots, but O(m) when no dots. Space: O(total characters).
Trie plus DFS for dots
What Trips People Up in Real Interviews
Not handling the wildcard dot correctly. A dot matches any character, so you need to try all 26 children recursively.
Confusing this with a standard trie search. The dot changes everything — you can't just follow one child.
Forgetting to check is_end when the search string is fully consumed. The traversal might complete but the word might not be in the dictionary.
Not handling the case where no branch matches a dot. Return false if none of the 26 children leads to a match.
Using BFS instead of DFS for wildcard search. BFS works but uses more memory storing all frontier nodes. DFS with recursion is more natural for trie traversal and prunes branches early on mismatches.
Solution Code
addWord: O(m), where m is the wo 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 ch in word:
if ch not in node.children:
node.children[ch] = TrieNode()
node = node.children[ch]
node.is_end = True
def search(self, word):
def dfs(node, i):
if i == len(word):
return node.is_end
ch = word[i]
if ch == '.':
for child in node.children.values():
if dfs(child, i + 1):
return True
return False
if ch not in node.children:
return False
return dfs(node.children[ch], 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 new words and finding if a string matches any previously added string. The search method can contain dots where a dot can match any letter.
How do you solve Design Add and Search Words Data Structure?
The optimal approach runs in addWord: O(m), where m is the wo time and O(total characters stored) for t 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 Google, Meta, Amazon, Microsoft, Apple. It is a medium difficulty problem.
What are common mistakes on Design Add and Search Words Data Structure?
- Not handling the wildcard dot correctly. A dot matches any character, so you need to try all 26 children recursively.
- Confusing this with a standard `trie` search. The dot changes everything — you can't just follow one child.
- Forgetting to check is_end when the search string is fully consumed. The traversal might complete but the word might not be in the dictionary.
- Not handling the case where no branch matches a dot. Return `false` if none of the 26 children leads to a match.
- Using BFS instead of DFS for wildcard search. BFS works but uses more memory storing all frontier nodes. DFS with recursion is more natural for `trie` traversal and prunes branches early on mismatches.