Design Add and Search Words Data Structure
Understanding the Problem
We need to build a dictionary that supports two operations: adding words and searching for them. Search queries can contain wildcard dots, where each dot matches any single letter. Searching for ".ad" should match "bad", "dad", "mad", or any three-letter word ending in "ad".
Without the wildcard, a hash set would be enough. With dots, we can't hash the query and look it up, because a pattern like "b.d" stands for 26 different strings. We have to match character by character, and at every dot position consider all possible characters.
This makes it a prefix-matching problem with branching: when we hit a dot, we explore multiple paths. A Trie (prefix tree) fits because it stores words character by character and lets a search branch at wildcard positions.
Key Constraints:
word.length <= 25→ Words are short. Each comparison or Trie walk touches at most 25 characters.At most 3 dots in search queries→ This caps the branching during a wildcard search: at most 3 positions fan out into up to 26 children each, so the search stays cheap.At most 10^4 calls→ Enough operations that scanning every stored word on every search becomes expensive.Lowercase English letters only→ 26-character alphabet, which bounds the Trie's branching factor.
Approach 1: Brute Force with List
Intuition
Store every added word in a list, and for each search query, check every stored word against the pattern. A stored word matches if it has the same length and every character either equals the pattern character or the pattern character is a dot.
This is correct and easy to implement, but every search scans the entire list, including words whose length can't match.
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.
The next approach organizes words by their characters in a tree, so a search only walks paths that can still match instead of scanning the whole list.
Approach 2: Trie with DFS for Wildcards
Intuition
A Trie (prefix tree) stores words character by character in a tree. Each node has up to 26 children (one per lowercase letter), and a node is 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 following its characters down the tree.
The dot wildcard maps onto this structure directly. For a regular character, we follow the single matching child (if it exists). For a dot, we try every existing child, and if any of those paths leads to a complete match, we return true. This is a DFS with backtracking: each dot branches into multiple paths, and we explore them recursively.
The branching is bounded in two ways. First, a query has at most 3 dots, so even the theoretical worst case is 26^3 = 17,576 paths. Second, we only descend into children that exist. If 3 stored words start with 'b' and 1,000 start with other letters, searching for "b.." follows 'b' once and then explores only the 3 surviving subtrees; the other 1,000 words are never touched. This pruning by shared prefix is what the list-based approach cannot do.
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 k dots, the worst case is O(26^k m). Since k is at most 3 and m is at most 25, that bound is 26^3 25, a small constant, and usually far smaller because only existing children are explored.
- Space Complexity: O(N * m) for the Trie 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, and shared prefixes reduce this in practice. The search recursion goes at most m levels deep, adding O(m) stack space.