Problem Description

This problem asks you to design a data structure called WordDictionary that can store words and search for them with a special wildcard feature.

The data structure needs to support two operations:

1. addWord(word): Adds a word to the dictionary. The word consists only of lowercase English letters.

2. search(word): Searches for a word in the dictionary. The search query can contain:

   • Regular lowercase English letters that must match exactly
   • The wildcard character '.' which can match any single letter

For example, if you add the words "bad", "dad", and "mad" to the dictionary:

• Searching for "bad" returns True (exact match exists)
• Searching for "pad" returns False (no exact match)
• Searching for ".ad" returns True (matches "bad", "dad", and "mad" where '.' can be 'b', 'd', or 'm')
• Searching for "b.." returns True (matches "bad" where the two dots match 'a' and 'd')

The solution uses a Trie (prefix tree) data structure to efficiently store and search words. Each node in the Trie has 26 children (one for each lowercase letter) and a flag indicating if it marks the end of a valid word.

The addWord operation traverses the Trie, creating nodes as needed for each character in the word, and marks the final node as a word ending.

The search operation uses recursion to handle the wildcard character '.'. When encountering a dot, it explores all possible branches in the Trie at that position. For regular characters, it follows the specific branch if it exists. The search succeeds if it reaches a node marked as a word ending after processing all characters.

Flowchart Walkthrough

First, let's pin down the algorithm using the Flowchart. Here's a step-by-step walkthrough:

Is it a graph?

• Yes: The Trie data structure is essentially a tree, which is a special type of graph. Each node represents a prefix, and edges represent character transitions.

Is it a tree?

• Yes: A Trie is specifically a tree structure where each node can have up to 26 children (one for each lowercase letter), and there's a single root node.

DFS

• Yes: The search operation, especially when handling the wildcard character '.', requires exploring multiple branches of the tree. When we encounter a '.', we need to recursively explore all possible child nodes, which is a classic depth-first search pattern.

Conclusion: The flowchart leads us to use DFS (Depth-First Search) for this problem. This makes perfect sense because:

1. The Trie is a tree structure that we need to traverse
2. The wildcard search requires exploring multiple paths when encountering '.'
3. DFS with backtracking allows us to explore each possible branch recursively and return true if any path matches the search pattern
4. The recursive nature of DFS perfectly handles the variable depth traversal needed for words of different lengths

Intuition

When we need to store and search for words efficiently, especially with pattern matching, we should think about how words share common prefixes. For instance, "bad", "bat", and "ban" all start with "ba". Instead of storing each word separately, we can build a tree-like structure where common prefixes are shared.

This naturally leads us to a Trie (prefix tree), where each path from root to a leaf represents a word. Each node stores whether it marks the end of a valid word, and has up to 26 children (one for each letter).

The real challenge comes with the wildcard search using '.'. When we encounter a regular letter, we simply follow the corresponding branch if it exists. But when we hit a '.', we need to explore all possible branches at that level since '.' can match any letter.

This "explore all possibilities" requirement screams for a recursive DFS approach. At each '.', we branch out to all existing children and continue searching from each one. If any branch leads to a successful match, we return True. This is essentially a backtracking pattern - we try one path, and if it doesn't work, we backtrack and try another.

The beauty of this approach is that the recursive DFS naturally handles the variable depth of the search (words of different lengths) and the branching factor when encountering wildcards. The recursion stack keeps track of our current position in both the search word and the Trie, making the implementation clean and intuitive.

For example, when searching for "b.." in a Trie containing "bad", we start at root, move to 'b', then at the first '.' we find child 'a' exists, move there, then at the second '.' we find child 'd' exists and it's marked as a word ending - success!

Solution Approach

The implementation consists of two classes: Trie and WordDictionary.

Trie Node Structure: Each Trie node contains:

• children: An array of 26 elements (for 'a' to 'z'), where children[i] points to the child node for character chr(ord('a') + i)
• is_end: A boolean flag indicating if this node marks the end of a valid word

Adding Words (addWord):

1. Start from the root of the Trie
2. For each character c in the word:
   • Calculate its index: idx = ord(c) - ord('a')
   • If node.children[idx] doesn't exist, create a new Trie node there
   • Move to the child node: node = node.children[idx]
3. After processing all characters, mark the final node with node.is_end = True

Searching with Wildcards (search): The search uses a recursive helper function that takes the remaining word to search and the current node:

1. Iterate through each character in the word:

   • If it's a regular letter and the corresponding child doesn't exist, return False
   • If it's a '.' wildcard:
     • Try all non-null children recursively
     • For each child, search the remaining substring word[i+1:] starting from that child
     • If any recursive call returns True, we found a match
     • If no child leads to a match, return False
   • If it's a regular letter with an existing child, move to that child

2. After processing all characters, return node.is_end to check if we've reached a valid word ending

Key Implementation Details:

• The wildcard handling uses DFS to explore all possible branches when encountering '.'
• The recursion naturally handles backtracking - if one branch fails, we try the next
• String slicing word[i+1:] passes the remaining portion of the word to recursive calls
• The base case occurs when we've processed all characters and check is_end

Time Complexity:

• addWord: O(m) where m is the length of the word
• search: O(n × 26^k) worst case, where n is the word length and k is the number of dots (since each dot requires exploring up to 26 branches)

Space Complexity:

• O(ALPHABET_SIZE × N × M) for storing the Trie, where N is the number of words and M is the average length

Example Walkthrough

Let's walk through a concrete example to see how the Trie-based solution works.

Step 1: Initialize and Add Words

Start with an empty WordDictionary and add three words: "bad", "dad", "mad"

Initial: root = Trie()

Adding "bad":
- Start at root
- 'b': Create child at index 1 (b-a=1), move there
- 'a': Create child at index 0 (a-a=0), move there  
- 'd': Create child at index 3 (d-a=3), move there
- Mark is_end = True

Adding "dad":
- Start at root
- 'd': Create child at index 3 (d-a=3), move there
- 'a': Create child at index 0, move there
- 'd': Create child at index 3, move there  
- Mark is_end = True

Adding "mad":
- Start at root
- 'm': Create child at index 12 (m-a=12), move there
- 'a': Create child at index 0, move there
- 'd': Create child at index 3, move there
- Mark is_end = True

The resulting Trie structure looks like:

       root
      / | \
    b   d   m
    |   |   |
    a   a   a
    |   |   |
    d*  d*  d*
  
(* indicates is_end = True)

Step 2: Search for ".ad"

Now let's search for the pattern ".ad" which should return True:

1. Start at root with word = ".ad", index = 0

2. First character is '.', so we need to try all non-null children of root

3. Root has three children at indices 1('b'), 3('d'), and 12('m')

   Branch 1: Try child 'b'

   • Recursively search for "ad" starting from the 'b' node
   • Next char 'a': Check children[0] of 'b' node → exists, move there
   • Next char 'd': Check children[3] of 'a' node → exists, move there
   • Reached end of pattern, check is_end → True
   • Return True (found "bad")

Since we found a match, the search returns True immediately without needing to check the other branches.

Step 3: Search for "b.."

Let's trace through searching for "b..":

1. Start at root with word = "b..", index = 0
2. First character is 'b': Check children[1] → exists, move to 'b' node
3. Second character is '.': Try all non-null children of 'b' node
   • 'b' node only has one child at index 0 ('a')
   Branch: Try child 'a'
   • Recursively search for "." starting from 'a' node
   • Next char is '.': Try all non-null children of 'a' node
   • 'a' node only has one child at index 3 ('d')
   Sub-branch: Try child 'd'
   • Recursively search for "" (empty) starting from 'd' node
   • No more characters to process
   • Check is_end of 'd' node → True
   • Return True (found "bad")

Step 4: Search for "b.d" (False case)

1. Start at root with word = "b.d", index = 0
2. First character is 'b': Check children[1] → exists, move to 'b' node
3. Second character is '.': Try all non-null children of 'b' node
   • Only child is at index 0 ('a'), so recursively search for "d" from 'a' node
4. From 'a' node, look for 'd': Check children[3] → exists, move to 'd' node
5. Reached end of pattern, check is_end → True
6. Return True (found "bad")

Wait, this should return True! Let me trace a false case instead:

Step 4 (corrected): Search for "ba" (False case)

1. Start at root with word = "ba", index = 0
2. First character is 'b': Check children[1] → exists, move to 'b' node
3. Second character is 'a': Check children[0] → exists, move to 'a' node
4. Reached end of pattern, check is_end of 'a' node → False (not a word ending)
5. Return False

This returns False because although the path "ba" exists in our Trie, it's not marked as a complete word - only "bad" is marked as complete.

Solution Implementation

Time and Space Complexity

Time Complexity:

• addWord(word): O(m) where m is the length of the word being added. We traverse through each character of the word exactly once, and for each character, we perform constant time operations (array indexing and node creation).

• search(word):

  • Best case: O(m) where m is the length of the search word, when there are no wildcard characters ('.'). We simply traverse down the trie following the exact path.
  • Worst case: O(n × 26^m) where m is the length of the search word and n is the total number of nodes in the trie. This occurs when the word consists entirely of wildcards ('.'). At each '.', we potentially explore all 26 branches, and for each branch, we recursively search the remaining substring. In the absolute worst case with all dots, we could explore 26^m different paths.
  • Average case with wildcards: O(n × 26^k) where k is the number of wildcard characters in the search word.

Space Complexity:

• addWord(word): O(m) in the worst case where m is the length of the word. If none of the characters in the word share a common prefix with existing words, we create m new Trie nodes.

• search(word): O(m) for the recursion stack depth, where m is the length of the search word. In the worst case with wildcards, the recursive calls can go as deep as the length of the word.

• Overall space complexity of the data structure: O(ALPHABET_SIZE × N × M) = O(26 × N × M) where N is the total number of words inserted and M is the average length of the words. Each Trie node contains an array of 26 pointers to children nodes. In the worst case where no words share common prefixes, we would have N × M nodes, each with a 26-element array.

Common Pitfalls

1. Inefficient String Slicing in Recursion

The most common performance pitfall in this solution is the use of string slicing word_substring[i + 1:] during recursive calls. This creates a new string object every time, leading to O(n) extra time and space complexity for each recursive call.

Problem Example:

# Current inefficient approach
if dfs_search(word_substring[i + 1:], child_node):  # Creates new string
    return True

Solution: Use an index pointer instead of string slicing:

def search(self, word: str) -> bool:
    def dfs_search(index: int, node: TrieNode) -> bool:
        # Base case: reached end of word
        if index == len(word):
            return node.is_end_of_word
      
        char = word[index]
      
        if char == '.':
            # Wildcard: try all possible children
            for child_node in node.children:
                if child_node is not None:
                    # Pass index+1 instead of slicing
                    if dfs_search(index + 1, child_node):
                        return True
            return False
        else:
            # Regular character
            char_index = ord(char) - ord('a')
            if node.children[char_index] is None:
                return False
            return dfs_search(index + 1, node.children[char_index])
  
    return dfs_search(0, self.root)

2. Forgetting to Handle Empty String Edge Case

The code doesn't explicitly handle the case where an empty string is added or searched. While the current implementation technically works (empty string returns True only if root.is_end_of_word is True), it's better to be explicit.

Solution: Add explicit checks:

def addWord(self, word: str) -> None:
    if not word:  # Handle empty string
        self.root.is_end_of_word = True
        return
    # ... rest of the implementation

def search(self, word: str) -> bool:
    if not word:  # Handle empty string
        return self.root.is_end_of_word
    # ... rest of the implementation

3. Not Optimizing the Wildcard Search

When encountering a wildcard, the current approach iterates through all 26 children even if many are None. This can be optimized by maintaining a list of actual children or checking early termination conditions.

Solution: Early termination and optimization:

def dfs_search(index: int, node: TrieNode) -> bool:
    if index == len(word):
        return node.is_end_of_word
  
    char = word[index]
  
    if char == '.':
        # Early termination: if this is the last character
        if index == len(word) - 1:
            # Just check if any child has is_end_of_word = True
            for child in node.children:
                if child and child.is_end_of_word:
                    return True
            return False
      
        # Continue searching for non-last characters
        for child in node.children:
            if child and dfs_search(index + 1, child):
                return True
        return False
    else:
        char_index = ord(char) - ord('a')
        if node.children[char_index] is None:
            return False
        return dfs_search(index + 1, node.children[char_index])

4. Memory Waste with Fixed-Size Arrays

Using [None] * 26 for every node wastes memory when words share few common prefixes or when the dictionary is sparse.

Solution: Use a dictionary instead of a fixed array:

class TrieNode:
    def __init__(self):
        self.children = {}  # Use dictionary instead of array
        self.is_end_of_word = False

def addWord(self, word: str) -> None:
    current_node = self.root
    for char in word:
        if char not in current_node.children:
            current_node.children[char] = TrieNode()
        current_node = current_node.children[char]
    current_node.is_end_of_word = True

These optimizations significantly improve both time and space efficiency, especially for large datasets with many wildcard searches.