Solving Design Add and Search Words in Python: Step-by-Step Guide

Design Add and Search Words in Python: Step-by-Step Guide

The "Design Add and Search Words" problem is a classic data structure challenge that frequently appears in coding interviews and real-world search applications. It asks you to design a system that supports adding new words and searching for existing words, with a special twist: the search function must support wildcard characters (typically the dot . character) that can match any letter. In this tutorial, we will walk through the problem, understand why it matters, build a solution from scratch using a Trie, and discuss best practices.

What Is the Problem?

The problem, popularized by LeetCode (Problem 211 - Design Add and Search Words Data Structure), requires you to implement a class WordDictionary with two main methods:

addWord(word): Adds a word to the data structure.
search(word): Returns True if the word exists in the data structure. The word may contain dots . where each dot can match any letter.

For example, after adding the words "bad", "dad", and "mad", a search for "pad" returns False, a search for "bad" returns True, and a search for ".ad" or "b.." also returns True because the dots match any character.

Why It Matters

This problem is important for several reasons. First, it teaches you how to design efficient data structures for string operations. Second, it introduces the Trie (prefix tree) data structure, which is foundational for autocomplete systems, spell checkers, and IP routing tables. Third, the wildcard search requirement forces you to think about tree traversal strategies, specifically depth-first search (DFS) with backtracking. Mastering this problem gives you a strong foundation for tackling more complex search and retrieval systems.

Understanding the Trie Data Structure

A Trie is a tree-like data structure where each node represents a character of a string. The root node is empty, and each path from the root to a node represents a prefix. Words are stored by traversing from the root, creating or following child nodes for each character. A special flag at a node indicates that a complete word ends there.

For the wildcard search, when we encounter a dot ., we must explore all possible child nodes at that level. This is where DFS comes into play: we recursively try every branch and return True if any path leads to a valid word match.

Step-by-Step Implementation

Let us build the solution step by step. We will create a TrieNode class and a WordDictionary class.

Step 1: Define the Trie Node

Each node needs a dictionary to store its children and a boolean flag to indicate whether it marks the end of a word.

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end = False

Step 2: Initialize the Word Dictionary

The WordDictionary class will hold a root TrieNode as the starting point for all operations.

class WordDictionary:
    def __init__(self):
        self.root = TrieNode()

Step 3: Implement addWord

To add a word, we start at the root and iterate through each character. For each character, if it does not exist in the current node's children, we create a new TrieNode. We move to the child node and continue. At the end of the word, we mark the final node's is_end flag as True.

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

Step 4: Implement search with Wildcard Support

The search method is more complex because of the wildcard character. When we encounter a regular character, we simply follow the corresponding child node. When we encounter a dot, we must recursively search all children. We use a helper function that performs DFS.

def search(self, word: str) -> bool:
    def dfs(index, node):
        for i in range(index, len(word)):
            char = word[i]
            if char == '.':
                # Try all possible children
                for child in node.children.values():
                    if dfs(i + 1, child):
                        return True
                return False
            else:
                if char not in node.children:
                    return False
                node = node.children[char]
        return node.is_end

    return dfs(0, self.root)

Complete Solution

Here is the complete, runnable solution combining all the pieces:

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end = False


class WordDictionary:
    def __init__(self):
        self.root = TrieNode()

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

    def search(self, word: str) -> bool:
        def dfs(index, node):
            for i in range(index, len(word)):
                char = word[i]
                if char == '.':
                    for child in node.children.values():
                        if dfs(i + 1, child):
                            return True
                    return False
                else:
                    if char not in node.children:
                        return False
                    node = node.children[char]
            return node.is_end

        return dfs(0, self.root)


# Example usage
if __name__ == "__main__":
    wd = WordDictionary()
    wd.addWord("bad")
    wd.addWord("dad")
    wd.addWord("mad")

    print(wd.search("pad"))   # False
    print(wd.search("bad"))   # True
    print(wd.search(".ad"))   # True
    print(wd.search("b.."))   # True
    print(wd.search("..."))   # True
    print(wd.search("b.d"))   # True
    print(wd.search("ba."))   # True
    print(wd.search("b..."))  # False

How to Use It

Using the WordDictionary class is straightforward. Instantiate the class, add words using addWord, and query using search. The search method accepts exact words and patterns with dots. Each dot represents exactly one character, similar to the single-character wildcard in regular expressions.

You can integrate this class into larger applications such as autocomplete systems, dictionary lookups, or games like crossword solvers where partial information is available.

Complexity Analysis

Understanding the time and space complexity helps you evaluate whether this solution fits your use case:

addWord: O(L) time, where L is the length of the word. Space is O(L) in the worst case for a new word with no shared prefixes.
search (no wildcards): O(L) time, as we simply traverse the Trie.
search (with wildcards): O(26^L) time in the worst case, where every character is a dot and every node has 26 children. In practice, the branching is much smaller because most nodes have far fewer children.
Space: O(N * L) where N is the number of words and L is the average word length, though shared prefixes reduce this significantly.

Best Practices

When implementing and using this data structure, keep the following best practices in mind:

Use dictionaries for children: In Python, using a dictionary for children is more memory-efficient than a fixed-size array of 26 elements, especially when the alphabet is not limited to lowercase English letters.
Consider an array for fixed alphabets: If you know the input only contains lowercase English letters, using a list of size 26 can be faster due to better cache locality, at the cost of slightly more memory.
Optimize wildcard search with early termination: The DFS approach already returns True as soon as a match is found, which prunes unnecessary branches.
Handle edge cases: Consider what happens with empty strings, duplicate words, or words with uppercase letters. You may want to normalize input by converting to lowercase.
Consider iterative DFS: For very deep Tries, recursive DFS may hit Python's recursion limit. An iterative approach using an explicit stack can avoid this issue.
Profile for large datasets: If you are storing millions of words, monitor memory usage and consider compressed Trie variants like a Radix Tree.

Alternative Approach: Iterative Search with a Stack

If recursion depth is a concern, you can rewrite the search method using an explicit stack. This avoids potential RecursionError on very long words:

def search(self, word: str) -> bool:
    stack = [(0, self.root)]
    while stack:
        index, node = stack.pop()
        if index == len(word):
            if node.is_end:
                return True
            continue
        char = word[index]
        if char == '.':
            for child in node.children.values():
                stack.append((index + 1, child))
        else:
            if char in node.children:
                stack.append((index + 1, node.children[char]))
    return False

This iterative version produces the same results but uses explicit stack management, making it safer for extremely long inputs.

Conclusion

The "Design Add and Search Words" problem is an excellent exercise in combining the Trie data structure with recursive search techniques. By building a Trie to store words efficiently and using DFS to handle wildcard characters, you create a flexible and powerful search system. Whether you are preparing for coding interviews or building a real-world search feature, understanding this solution equips you with the skills to handle prefix-based and pattern-based string queries. Remember to consider your specific use case when choosing between recursive and iterative approaches, and always test edge cases to ensure robustness.