Design Add and Search Words Data Structure
Problem
Design a data structure that supports adding new words and searching for a word, where the search word may contain the dot character '.' to represent any one letter.
- 1 ≤ word.length ≤ 500
- word in addWord consists of lowercase English letters
- word in search consists of '.' or lowercase English letters
- At most 3 * 10⁴ calls will be made to addWord and search
Example
addWord("bad"), addWord("dad"), addWord("mad"), search("pad"), search("bad"), search(".ad"), search("b..")[null, null, null, false, true, true, true]Words "bad", "dad", and "mad" are added to the data structure. Searching for "pad" returns false because it was not added. Searching for "bad" returns true as it was added. Searching for ".ad" returns true because '.' matches any letter and "bad", "dad", and "mad" all match. Searching for "b.." returns true because it matches "bad".
Approach
Straightforward Solution
A brute-force approach would store all words in a list and check each word against the search pattern, which is inefficient (O(n*m) where n is number of words and m is word length) and does not scale well.
Core Observation
A Trie is a tree-like data structure that stores words by sharing common prefixes, enabling efficient prefix-based queries. The wildcard '.' introduces branching in the search, requiring exploration of all possible child nodes at that position.
Path to Optimal
The key recognition signals are 'add words' and 'search with wildcard .', which indicate a Trie data structure with backtracking search. The Trie allows prefix sharing and fast traversal, while the '.' wildcard requires a DFS exploring all children at that position. This combination efficiently handles both exact and wildcard searches.
Optimal Approach
Implement a TrieNode class with a dictionary of children and an end_of_word flag. For addWord, insert characters sequentially, creating nodes as needed. For search, use a recursive DFS that, at each character, either follows the exact child node or, if '.', recursively explores all children. Return true if any path matches the entire word and ends at a node marked as end_of_word.
Time
O(m * 26^k)
In the worst case, the search explores all possible branches for each '.' wildcard, where m is the length of the word and k is the number of wildcards. Each wildcard can branch into up to 26 children, leading to exponential branching in k. However, typical usage and pruning make this efficient in practice.
Space
O(n * m)
The Trie stores all added words, with each character represented as a node. In the worst case, all words are distinct with no shared prefixes, leading to O(n*m) nodes, where n is the number of words and m is the average word length.
Pattern Spotlight
Trie (Prefix Tree) with Backtracking for Wildcard Search
When searching with wildcards in a prefix tree, use DFS to explore all possible child nodes at wildcard positions, enabling flexible pattern matching while leveraging prefix sharing for efficiency.
Solution
| 1 | class TrieNode:
|
| 2 | def __init__(self):
|
| 3 | self.children = {}
|
| 4 | self.end_of_word = False
|
| 5 |
|
| 6 | class WordDictionary:
|
| 7 | def __init__(self):
|
| 8 | self.root = TrieNode()
|
| 9 |
|
| 10 | def addWord(self, word: str) -> None:
|
| 11 | curr = self.root
|
| 12 | for c in word:
|
| 13 | if c not in curr.children:
|
| 14 | curr.children[c] = TrieNode()
|
| 15 | curr = curr.children[c]
|
| 16 | curr.end_of_word = True
|
| 17 |
|
| 18 | def search(self, word: str) -> bool:
|
| 19 | def dfs(j, root):
|
| 20 | curr = root
|
| 21 | for i in range(j, len(word)):
|
| 22 | c = word[i]
|
| 23 | if c == ".":
|
| 24 | for child in curr.children.values():
|
| 25 | if dfs(i + 1, child):
|
| 26 | return True
|
| 27 | return False
|
| 28 | else:
|
| 29 | if c not in curr.children:
|
| 30 | return False
|
| 31 | curr = curr.children[c]
|
| 32 | return curr.end_of_word
|
| 33 |
|
| 34 | return dfs(0, self.root) |
| 1 | class WordDictionary { |
| 2 | private static class TrieNode { |
| 3 | Map<Character, TrieNode> children = new HashMap<>(); |
| 4 | boolean endOfWord = false; |
| 5 | } |
| 6 | |
| 7 | private final TrieNode root; |
| 8 | |
| 9 | public WordDictionary() { |
| 10 | root = new TrieNode(); |
| 11 | } |
| 12 | |
| 13 | public void addWord(String word) { |
| 14 | TrieNode curr = root; |
| 15 | for (char c : word.toCharArray()) { |
| 16 | if (!curr.children.containsKey(c)) { |
| 17 | curr.children.put(c, new TrieNode()); |
| 18 | } |
| 19 | curr = curr.children.get(c); |
| 20 | } |
| 21 | curr.endOfWord = true; |
| 22 | } |
| 23 | |
| 24 | public boolean search(String word) { |
| 25 | return dfs(word, 0, root); |
| 26 | } |
| 27 | |
| 28 | private boolean dfs(String word, int j, TrieNode node) { |
| 29 | TrieNode curr = node; |
| 30 | for (int i = j; i < word.length(); i++) { |
| 31 | char c = word.charAt(i); |
| 32 | if (c == '.') { |
| 33 | for (TrieNode child : curr.children.values()) { |
| 34 | if (dfs(word, i + 1, child)) { |
| 35 | return true; |
| 36 | } |
| 37 | } |
| 38 | return false; |
| 39 | } else { |
| 40 | if (!curr.children.containsKey(c)) { |
| 41 | return false; |
| 42 | } |
| 43 | curr = curr.children.get(c); |
| 44 | } |
| 45 | } |
| 46 | return curr.endOfWord; |
| 47 | } |
| 48 | } |
Step-by-Step Solution
Build Trie Nodes and Insert Words to Share Prefixes
| 3 | self.children = {}
|
| 4 | self.end_of_word = False
|
| 8 | self.root = TrieNode()
|
| 11 | curr = self.root
|
| 12 | for c in word:
|
| 13 | if c not in curr.children:
|
| 14 | curr.children[c] = TrieNode()
|
| 15 | curr = curr.children[c]
|
| 16 | curr.end_of_word = True
|
Objective
To construct a prefix tree that stores all added words efficiently by sharing common prefixes.
Key Insight
A TrieNode holds a dictionary of children nodes keyed by characters and a flag indicating if a word ends at that node. Adding a word involves traversing or creating nodes for each character, enabling fast prefix-based storage and lookup. This structure reduces redundant storage and accelerates searches compared to a flat list.
Interview Quick-Check
Core Logic
Each character in the word corresponds to a child node in the Trie, creating a path that represents the word.
State & Boundaries
Marking the end_of_word flag at the last character node distinguishes complete words from prefixes.
Common Pitfalls & Bugs
Forgetting to create a new TrieNode when a character is not present leads to incorrect or incomplete Trie construction.
Explore Trie Recursively to Match Words with Wildcards
| 19 | def dfs(j, root):
|
| 20 | curr = root
|
| 21 | for i in range(j, len(word)):
|
| 22 | c = word[i]
|
| 23 | if c == ".":
|
| 24 | for child in curr.children.values():
|
| 25 | if dfs(i + 1, child):
|
| 26 | return True
|
| 27 | return False
|
| 28 | else:
|
| 29 | if c not in curr.children:
|
| 30 | return False
|
| 31 | curr = curr.children[c]
|
| 32 | return curr.end_of_word
|
| 34 | return dfs(0, self.root) |
Objective
To perform a depth-first search on the Trie that supports '.' wildcard matching by exploring all possible child nodes at wildcard positions.
Key Insight
The search function uses recursion to traverse the Trie from a given node and index. When encountering a '.', it recursively explores all children nodes, effectively branching the search. For normal characters, it follows the corresponding child node if it exists. This approach combines Trie traversal efficiency with backtracking to handle flexible pattern matching.
Interview Quick-Check
Core Logic
DFS explores all possible paths when encountering '.', ensuring all valid matches are found without prematurely pruning.
State & Boundaries
The recursion terminates when the end of the word is reached, returning whether the current node marks a complete word.
Common Pitfalls & Bugs
Returning False immediately when a character is not found prevents unnecessary exploration and ensures correctness.
Complexity
The recursive search may branch exponentially with the number of wildcards, but pruning and prefix sharing mitigate this in practice.
Line Analysis
This solution has 5 Critical lines interviewers watch for.
curr.end_of_word = TrueMark the current node as the end of a word after insertion.
This line is critical because it distinguishes complete words from mere prefixes, enabling accurate search results that differentiate between partial and full matches.
if c == ".":Check if the current character is a wildcard '.'
This conditional is the core of wildcard handling; it forces exploration of all children nodes, which is essential to correctly match any letter at this position.
if dfs(i + 1, child):Recursively search the remainder of the word from the next index and child node.
This recursive exploration is the heart of the backtracking search, enabling the algorithm to find any valid word matching the pattern by trying all possible continuations.
if c not in curr.children:Check if the character is not present among the current node's children.
This check is critical to avoid false positives; it ensures the search only continues along valid paths that exist in the Trie.
return curr.end_of_wordReturn whether the current node marks the end of a valid word after full traversal.
Returning the end_of_word flag here is essential to distinguish between partial matches and full word matches, ensuring search correctness.
self.children = {}Initialize the children dictionary for the TrieNode.
This dictionary stores mappings from characters to child TrieNodes, enabling efficient traversal and insertion of words sharing prefixes.
if c not in curr.children:Check if the current character is not already a child of the current node.
Detecting missing nodes triggers creation of new TrieNodes, expanding the Trie to accommodate new words.
curr.children[c] = TrieNode()Create a new TrieNode for the missing character.
Adding a new node preserves the Trie structure and enables future searches to find this character path.
for child in curr.children.values():Iterate over all child nodes of the current Trie node.
Exploring all children allows the search to consider every possible letter substitution for the wildcard.
return TrueReturn True immediately if any recursive path matches.
Early termination upon finding a valid match improves efficiency by pruning unnecessary exploration.
return FalseReturn False if no child paths match the wildcard.
This ensures the search correctly fails when no valid substitutions exist for the wildcard at this position.
return FalseReturn False immediately if the character is not found.
Early termination prevents unnecessary recursion and correctly signals no match for the current path.
self.end_of_word = FalseInitialize the end_of_word flag to False.
This flag marks whether the current node corresponds to the end of a valid word, distinguishing prefixes from complete words.
self.root = TrieNode()Create the root TrieNode for the WordDictionary.
The root node serves as the entry point for all word insertions and searches, representing an empty prefix.
curr = curr.children[c]Move the current pointer to the child node corresponding to the character.
Advancing the pointer allows sequential insertion or traversal along the word's path.
def dfs(j, root):Define the recursive DFS helper function for searching.
Encapsulating the search logic in a recursive function allows elegant handling of wildcards and branching.
else:Handle the case where the character is not a wildcard.
Normal characters require exact matching in the Trie children to continue the search.
curr = curr.children[c]Advance the current node pointer to the child node matching the character.
Moving forward in the Trie aligns the search with the word's characters, maintaining correctness.
return dfs(0, self.root)Initiate the search from the root node starting at index 0.
This call triggers the recursive DFS search over the entire word from the root of the Trie.
curr = self.rootStart traversal from the root node to add a new word.
Insertion begins at the root, progressing character by character to build or follow existing paths in the Trie.
curr = rootInitialize the current node pointer for traversal.
Starting from the given root node ensures the search explores the correct subtree corresponding to the current recursion state.
for c in word:Iterate over each character in the word to insert.
Sequentially processing characters ensures the word is represented as a path in the Trie.
for i in range(j, len(word)):Iterate over the characters of the word starting from index j.
Processing characters sequentially aligns with the Trie structure and supports partial pattern matching.
c = word[i]Extract the current character from the word.
Isolating the character allows conditional logic to handle normal letters and wildcards distinctly.
Test Your Understanding
Why does the search function use DFS and explore all children when encountering a '.' character?
Because '.' can match any letter, the search must explore all possible child nodes at that position to find any valid word matching the pattern. This exhaustive exploration ensures no potential matches are missed.
Related Problems
Tries pattern
Don't just read it. Drill it.
Reconstruct Design Add and Search Words Data Structure from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.
Unlock the Design Add and Search Words Data Structure drill