Domain 2MediumCORE

Design Add and Search Words Data Structure

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 search would be $O(N cdot L)$ 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 $ge 1$), handling wildcards correctly without traversing non-existent branches in the trie to avoid unnecessary work.

Domain: Medium•Updated: 2026-08-31
#Algorithms#LeetCode#qwen3.5:9b#Backtracking#Depth-first Search#Design#Trie

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 search would be O(N⋅L)O(N \cdot L) 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 ≥1\ge 1), 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 O(N⋅L)O(N \cdot L) per query where N is total added words. With 50k calls, this becomes too slow (NN 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

  1. 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.
  2. 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 = True on the final node. Time complexity is O(L)O(L) where L is word length.
  3. 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 True only if is_end is True at that specific node.

Complexity Analysis

  • Time Complexity:
    • addWord: O(L)O(L) 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 (O(26k)O(26^k) 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 O(L⋅10)O(L \cdot 10) 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: O(K⋅L)O(K \cdot L) (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 word in search matches exactly an added word (e.g., “bad” vs ”.”), the recursion hits base case and checks is_end.
  • No match found: Returns False immediately if a path is dead-ended before reaching end of string or without hitting is_end = True.
  • Duplicate words: The Trie naturally handles duplicates by reusing existing nodes; only the final node’s is_end matters, so adding “bad” twice works correctly.