LeetCode 211: Design Add and Search Words Data Structure Solution in Python Explained

Problem Statement

In LeetCode 211: Design Add and Search Words Data Structure, you need to implement a WordDictionary class with two methods:

• WordDictionary(): Initializes the data structure.
• void addWord(String word): Adds a word to the structure.
• boolean search(String word): Returns true if the word (with . as a wildcard for any letter) is in the structure, false otherwise.

This builds on LeetCode 208: Implement Trie (Prefix Tree) by adding wildcard search, differing from scheduling in LeetCode 210: Course Schedule II.

Constraints

• 1 ≤ word.length ≤ 25.
• word in addWord contains only lowercase English letters.
• word in search contains lowercase letters and ..
• At most 10⁴ calls to addWord and search.

Examples

Let’s see a sequence of operations:

Copy codeWordDictionary wordDictionary = new WordDictionary();
wordDictionary.addWord("bad");      // Adds "bad"
wordDictionary.addWord("dad");      // Adds "dad"
wordDictionary.addWord("mad");      // Adds "mad"
wordDictionary.search("pad");       // Returns false
wordDictionary.search("bad");       // Returns true
wordDictionary.search(".ad");       // Returns true
wordDictionary.search("b..");       // Returns true

This shows adding words and searching with wildcards.

Understanding the Problem

How do we solve LeetCode 211: Design Add and Search Words Data Structure in Python? We need a Trie where addWord("bad") stores the word, and search(".ad") checks all possibilities (e.g., bad, dad, mad). A naive approach might store a list and regex-match, but that’s slow. We’ll use a Trie with recursive search for wildcards: 1. Trie with Dictionary: O(m) for addWord, O(26^m) worst-case for search, O(m) space—our best solution (m = word length). 2. Trie with Array: Similar time and space, with a fixed structure.

Let’s explore the best solution.

Best Solution: Trie with Dictionary Approach

Explanation

The Trie with Dictionary approach uses a nested dictionary:

• Each node is a dictionary mapping characters to child nodes.
• A special key ('#') marks word ends.
• addWord: Insert characters, mark the end.
• search: Recursively traverse:
• For letters, follow the path.
• For ., explore all children.

It’s O(m) for addWord, O(26^m) for search with many wildcards (exponential due to branching), and O(m) space per word, making it Pythonic and efficient—our best solution.

For ["bad", "dad"], it handles search("b..") by checking all paths.

Step-by-Step Example

Example 1: Operations Sequence

Goal: Implement and test the structure.

• Step 1: WordDictionary()
• Root = {{.
• Step 2: addWord("bad")
• {'b': {'a': {'d': {'#': True{{{{.
• Step 3: addWord("dad")
• {'b': {'a': {'d': {'#': True{{{, 'd': {'a': {'d': {'#': True{{{{.
• Step 4: addWord("mad")
• {'b': {'a': {'d': {'#': True{{{, 'd': {'a': {'d': {'#': True{{{, 'm': {'a': {'d': {'#': True{{{{.
• Step 5: search("pad")
• p not in root, return false.
• Step 6: search("bad")
• b → a → d → '#', return true.
• Step 7: search(".ad")
• .: Try b, d, m:
• b → a → d → '#', true, return true.
• Step 8: search("b..")
• b → a → d → '#', true, return true.

How the Code Works (Trie with Dictionary) – Detailed Line-by-Line Explanation

Here’s the Python code with a detailed breakdown:

Copy codeclass WordDictionary:
    def __init__(self):
        # Line 1: Initialize root
        self.root = {{
        # Empty dict as root (e.g., {{)
        self.end = '#'
        # Word end marker (e.g., '#')

    def addWord(self, word: str) -> None:
        # Line 2: Start at root
        node = self.root
        # Current node (e.g., {{)

        # Line 3: Insert word
        for char in word:
            # Iterate chars (e.g., 'b', 'a', 'd')
            node = node.setdefault(char, {{)
            # Get or create child (e.g., {'b': {{{)
        node[self.end] = True
        # Mark end (e.g., {'#': True{)

    def search(self, word: str) -> bool:
        # Line 4: Start recursive search
        def dfs(node, i):
            # Helper: node = current node, i = index in word
            if i == len(word):
                # Reached end of word (e.g., i = 3)
                return self.end in node
                # True if word ends here (e.g., '#')

            if word[i] == '.':
                # Wildcard (e.g., '.')
                for child in node:
                    # Try all children (e.g., 'a', 'd')
                    if child != self.end and dfs(node[child], i + 1):
                        # Skip '#' and recurse (e.g., true)
                        return True
                return False

            if word[i] not in node:
                # Char not found (e.g., 'p')
                return False
            return dfs(node[word[i]], i + 1)
            # Follow path (e.g., 'b' → next node)

        return dfs(self.root, 0)
        # Start at root, index 0 (e.g., true for "bad")

This solution handles wildcards with recursion.

Alternative: Trie with Array Approach

Explanation

The Trie with Array approach uses a fixed 26-slot array per node:

• Each node has a 26-element array (for a-z) and an is_end flag.
• Map characters to indices (ord(char) - ord('a')).
• addWord: Build path as before.
• search: Recurse, exploring all slots for ..

It’s O(m) for addWord, O(26^m) for search with wildcards, and O(26m) space, offering a classic Trie structure.

Step-by-Step Example

For addWord("bad"), search(".ad"):

• Root: children[1] = node (for ‘b’), build b-a-d, is_end = True.
• .ad: Check all slots at root, b → a → d, true.

How the Code Works (Array)

Copy codeclass TrieNode:
    def __init__(self):
        self.children = [None] * 26
        self.is_end = False

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

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

    def search(self, word: str) -> bool:
        def dfs(node, i):
            if i == len(word):
                return node.is_end
            if word[i] == '.':
                for child in node.children:
                    if child and dfs(child, i + 1):
                        return True
                return False
            idx = ord(word[i]) - ord('a')
            if not node.children[idx]:
                return False
            return dfs(node.children[idx], i + 1)

        return dfs(self.root, 0)

Complexity

• Trie with Dictionary:
• Time: O(m) for addWord, O(26^m) for search (wildcards).
• Space: O(m) per word – dynamic allocation.
• Trie with Array:
• Time: O(m) for addWord, O(26^m) for search.
• Space: O(26m) per word – fixed array.

Efficiency Notes

Trie with Dictionary is our best solution for its space efficiency and Pythonic design. Trie with Array uses more memory but aligns with traditional Trie implementations.

Key Insights

• Wildcard: Requires branching.
• Trie: Prefix-based search.
• Recursion: Handles . elegantly.

Additional Example

For ["cat", "car"]:

• search("ca."): True (matches both).
• search("c.t"): True (matches "cat").

Edge Cases

• Single char: addWord("a"), search("."), true.
• All wildcards: search("..."), checks all paths.
• Empty (not per constraints): Assume false.

Both handle these well.

Final Thoughts

LeetCode 211: Design Add and Search Words Data Structure in Python is a fantastic Trie challenge with wildcards. Trie with Dictionary excels in flexibility, while Trie with Array offers a classic approach. Want more? Try LeetCode 208: Implement Trie (Prefix Tree) or LeetCode 212: Word Search II. Test your skills—Solve LeetCode 211 on LeetCode with ["bad","dad"], search(".ad") (expecting true)—search those words today!