Design Add and Search Words Data Structure
Last Updated: April 4, 2026
Understanding the Problem
We need to build a dictionary that supports two operations: adding words and searching for them. The twist is that search queries can contain wildcard dots, where each dot matches any single letter. So searching for ".ad" should match "bad", "dad", "mad", or any three-letter word ending in "ad".
Without the wildcard, this would be trivial: just use a hash set. But the dot wildcard changes everything. If we search for "b.d", we can't just hash the string and look it up. We need to match character by character, and at every dot position, we need to consider all possible characters.
The key observation is that this is fundamentally a prefix-matching problem with branching. When we hit a dot, we need to explore multiple paths. A Trie (prefix tree) is the natural data structure for this, because it lets us walk through the word character by character and branch at wildcard positions.
Key Constraints:
word.length <= 25→ Words are short. Even exponential branching on a 25-character word is manageable.At most 3 dots in search queries→ This is the critical constraint. It caps the branching factor during search. With at most 3 dots, we branch into at most 26 children at most 3 times, which keeps the search tractable.At most 10^4 calls→ Moderate number of operations. We don't need an exotic data structure, but we do need something better than scanning all stored words on every search.Lowercase English letters only→ 26-character alphabet, which bounds the Trie's branching factor.
Approach 1: Brute Force with List
Intuition
The simplest approach: store all added words in a list, and for each search query, check every stored word to see if it matches the pattern. Two words "match" if they have the same length and every character either matches exactly or the search character is a dot.
This is correct and easy to implement, but it scans through all stored words on every search call. If we've added thousands of words, that adds up quickly.
Algorithm
- Maintain a list of all words that have been added.
- For
addWord(word): append the word to the list. - For
search(word): iterate through every stored word. For each stored word, check if it has the same length as the search pattern. If so, compare character by character: if the search character is a dot, it matches anything; otherwise, the characters must be equal. If all characters match, return true. - If no stored word matches, return false.
Example Walkthrough
Code
- Time Complexity: O(n * m) per search, where n is the number of stored words and m is the length of the search pattern. We check every stored word and compare up to m characters each. addWord is O(1).
- Space Complexity: O(n * m) total, where n is the number of words added and m is the average word length. We store every word as-is.
On every search call, we scan through every single word we've ever added. Most words won't even have the right length. What if we organized words by their characters so that we only explore paths that could actually match?
Approach 2: Trie with DFS for Wildcards
Intuition
A Trie (prefix tree) stores words character by character in a tree structure. Each node has up to 26 children (one per lowercase letter), and nodes are marked as "end of word" where a complete word terminates. Adding a word means walking down the tree, creating nodes as needed. Searching for an exact word means walking down the tree following the characters.
The beauty of a Trie for this problem is how naturally it handles the dot wildcard. For regular characters, we follow the single matching child (if it exists). When we hit a dot, we try all existing children. If any of those paths leads to a complete match, we return true.
This is essentially a DFS with backtracking: at each dot, we branch into multiple paths and explore them recursively. The constraint that search queries have at most 3 dots keeps this manageable. Without dots, search is O(m) where m is the word length. With k dots, the worst case branches into 26^k paths, but k is at most 3, so that's 26^3 = 17,576 paths. In practice it's much less because most children don't exist.
The Trie organizes words by their shared prefixes. When we search for "b.d", we follow 'b' to narrow down to words starting with 'b', then at the dot we branch to all second-character options, and finally we check if 'd' exists at the third level. This prunes the search space dramatically compared to checking every stored word.
The recursion handles dots naturally. At each level, we either follow one path (regular character) or fan out to all paths (dot). The key insight is that even with branching, we're only exploring paths that actually exist in the Trie. If we've added 3 words starting with 'b' and 1000 starting with other letters, searching for "b.." only explores 3 paths at the first branch, not 1000.
Algorithm
- Build a Trie with a root node. Each node has an array of 26 children (initially null) and a boolean
isEndflag. - For
addWord(word): start at the root. For each character in the word, compute the index (char - 'a'). If the child at that index doesn't exist, create a new node. Move to the child. After the last character, mark the current node asisEnd = true. - For
search(word): use a recursive helperdfs(node, word, index). At each step: - If
index == word.length, returnnode.isEnd(we've matched all characters, check if it's a complete word). - If the current character is a dot, iterate through all 26 children. For each non-null child, recursively search from that child with
index + 1. If any returns true, return true. - If the current character is a letter, check the corresponding child. If it exists, recurse from that child. Otherwise, return false.
Example Walkthrough
Code
- Time Complexity: O(m) per addWord where m is the word length. O(m) per search for patterns without dots. For patterns with dots, worst case is O(26^k m) where k is the number of dots. Since k is at most 3, this is O(26^3 m) = O(17,576 * 25), effectively constant.
- Space Complexity: O(N * m) in the worst case, where N is the number of words and m is the average word length. Each character in each word creates at most one Trie node. Shared prefixes reduce this significantly in practice.