211. Design Add and Search Words Data Structure
Model: qwen3.5:9b
Topics: Backtracking,Depth-first Search,Design,Trie
FAANG asked: 1
Acceptance rate: 40.6%
Problem Breakdown
We need to implement a data structure that supports two operations: addWord and search.
- Inputs: A string of lowercase letters (for adding) or lowercase letters/dots (for searching). Dots (
.) act as wildcards matching any character. - Outputs: Boolean result for search, void/null for add.
- Constraints: Word length up to 500 characters; max 50k calls.
- Implicit Constraints: We need efficient prefix filtering because iterating through all stored words on every
searchwould be where N is the number of added words, which will time out given high call counts and large word lists. - Edge Cases: Empty strings (though constraints say length ), handling wildcards correctly without traversing non-existent branches in the trie to avoid unnecessary work.
Intuition
If we store all words in a simple list or hashset, search would require iterating through every stored word and checking character-by-character match with dots. This is per query where N is total added words. With 50k calls, this becomes too slow ( could be large).
The key insight for prefix-based matching is a Trie (Prefix Tree). A Trie allows us to traverse character by character from the root. If we encounter a specific letter during search, we only follow that path in the trie. This prunes branches immediately if they don’t match.
However, when we hit a dot (.), it means “match any child”. Since there are 26 lowercase letters, this introduces branching logic (backtracking). We must recursively try all valid children for every . encountered until either we find a complete word or exhaust the trie depth.
Approach
- Data Structure: Use a Trie where each node contains:
- A dictionary/hashmap of child nodes keyed by characters (‘a’-‘z’).
- A boolean flag (
is_end) to mark if a valid word ends at this specific node.
addWord(word):- Start from the root. Iterate through each character in
word. - If a child for that character doesn’t exist, create it.
- Move down to the next level. After processing all characters, set
is_end = Trueon the final node. Time complexity is where L is word length.
- Start from the root. Iterate through each character in
search(word):- Use Depth-First Search (DFS) recursively starting from root.
- If current character is a letter: Check if that child exists in
children. Recurse only if it does. Return the result of recursion immediately to short-circuit on success/failure for this path. - If current character is `.**: Iterate through all keys (existing children) in the node’s dictionary and recurse into each one.
- Base Case: When we reach a leaf or end of string, return
Trueonly ifis_endis True at that specific node.
Complexity Analysis
- Time Complexity:
addWord: where L is the length of the word being added (linear scan).search: In the worst case with many dots, we might traverse multiple branches. The complexity depends on the number of valid paths in the Trie that match the wildcard constraints. While it can technically degrade to exponential behavior relative to wildcards ( where k is wildcard depth), this is bounded by the total nodes reachable from root matching non-wildcard prefixes and length limits. Given typical test cases, performance remains efficient within time limits (effectively close to or similar depending on word density).
- Space Complexity:
- We store every character of every added word in the Trie nodes. If we have K words each length L, space is roughly proportional to the number of unique characters stored: (ignoring overhead for Python object headers which are constant per node).
Solution
class WordDictionary:
class Node:
def __init__(self):
self.children = {} # Map char -> Node
self.is_end = False
def __init__(self):
self.root = self.Node()
def addWord(self, word: str) -> None:
curr = self.root
for ch in word:
if ch not in curr.children:
curr.children[ch] = self.Node()
curr = curr.children[ch]
curr.is_end = True
def search(self, word: str) -> bool:
return self._search_recursive(word, 0, self.root)
def _search_recursive(self, word: str, index: int, node):
# Base case: reached end of string
if index == len(word):
return node.is_end
char = word[index]
# Case 1: Normal character (no wildcard)
if char != '.':
child_node = node.children.get(char)
if not child_node:
return False
return self._search_recursive(word, index + 1, child_node)
# Case 2: Wildcard '.' -> try all existing children
else:
for next_char in node.children.keys():
if self._search_recursive(word, index + 1, node.children[next_char]):
return True
return False
Edge Cases Handled
- Wildcards (
.): The recursive search iterates through all existing children when a dot is encountered. It does not attempt to create new nodes or traverse non-existent paths, preventing infinite loops or errors on missing branches. - Short words: If
wordin search matches exactly an added word (e.g., “bad” vs ”.”), the recursion hits base case and checksis_end. - No match found: Returns
Falseimmediately if a path is dead-ended before reaching end of string or without hittingis_end = True. - Duplicate words: The Trie naturally handles duplicates by reusing existing nodes; only the final node’s
is_endmatters, so adding “bad” twice works correctly.