Design Add and Search Words Data Structure
Asked at Google, Meta, Amazon, Microsoft, Apple
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.
Asked At
| 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.
Visual walkthrough for search "a.c":
Start at root. Char 'a' → follow 'a' child.
Char '.' → try all children of 'a' node: 'b', 'd', etc.
Try 'b': next char 'c' → follow 'c' child → check is_end. If true, return true.
Try 'd': next char 'c' → follow 'c' child → check is_end. If false, continue.
If any branch returns true, the word exists.
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).
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
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 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 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 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.