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

LeetCode 211: Design Add and Search Words Data Structure is a Medium trie problem. This Python walkthrough develops a trie plus wildcard DFS solution, ties every code decision to a concrete invariant, and includes the regression check used before publication.

This independent guide paraphrases the task rather than reproducing LeetCode’s prompt. Use the official page for the exact statement, examples, constraints, and submission runner.

Recognizing the pattern

A trie shares storage and work across common prefixes, allowing a search to abandon an entire family of words after one failed edge.

For this problem specifically, insert normally. During search, a dot branches to every child while a letter follows one matching edge. The invariant worth writing beside the code is: The DFS states represent all trie nodes consistent with the processed pattern prefix.

Step-by-step algorithm

1. Identify the input state consumed by addWord(word) and initialize the data required by the trie plus wildcard DFS pattern.
2. Insert normally. During search, a dot branches to every child while a letter follows one matching edge.
3. After each update, verify the page’s central invariant: The DFS states represent all trie nodes consistent with the processed pattern prefix.
4. Finish only after the boundary behavior is covered: A wildcard matches exactly one character, and a match must end at a terminal node.

Python solution

class WordDictionary:
    def __init__(self):
        self.root = {}

    def addWord(self, word):
        node = self.root
        for char in word: node = node.setdefault(char, {})
        node["$"] = True

    def search(self, word):
        def match(index, node):
            if index == len(word): return "$" in node
            char = word[index]
            if char == ".":
                return any(key != "$" and match(index + 1, child) for key, child in node.items())
            return char in node and match(index + 1, node[char])
        return match(0, self.root)

Reading the implementation

The main entry point is addWord(word). The named working state includes node, char; those variables make the trie plus wildcard DFS state visible instead of hiding it in incidental control flow.

A single main loop advances the algorithm, which is the key reason the traversal does not revisit already resolved input unnecessarily. Early returns stop as soon as the answer is forced, avoiding work that cannot change the result. In concrete terms, insert normally. During search, a dot branches to every child while a letter follows one matching edge.

Correctness argument

Initialization. The data structure starts with exactly the information known before any input element is processed.

Preservation. Insert normally. During search, a dot branches to every child while a letter follows one matching edge. Each update records the current item without invalidating earlier decisions; consequently, the DFS states represent all trie nodes consistent with the processed pattern prefix.

Termination. The traversal consumes a finite input or finite state space. At the end, the invariant covers the complete input, which is precisely the condition required for the returned result.

Complexity and trade-offs

O(L) insert and O(branching^wildcards) worst-case search time. The auxiliary-space figure excludes the returned output unless the output itself is the structure being built.

A hash set is simpler for exact words, but it cannot answer prefix or wildcard traversal without examining many candidates. That comparison is useful in an interview because it explains why the final implementation is preferable, not merely that it passes.

Regression check

The published implementation belongs to a 100-problem suite that is compiled and exercised behaviorally before deployment.

One reference assertion from that suite is shown below. It targets the normal path while the edge conditions in the next section cover the failure-prone boundaries.

wd=WordDictionary(); [wd.addWord(word) for word in ["bad","dad","mad"]]; assert wd.search(".ad") and not wd.search("pad")

Common mistakes and edge cases

• Problem-specific boundary: A wildcard matches exactly one character, and a match must end at a terminal node.
• Pattern-level pitfall: A prefix node is not necessarily a complete word; terminal markers and wildcard branching need separate handling.
• Invariant check: after every update, confirm that the DFS states represent all trie nodes consistent with the processed pattern prefix.

Interview review checklist

• Explain why trie plus wildcard DFS matches the structure of this input.
• State the invariant in one sentence before tracing code: The DFS states represent all trie nodes consistent with the processed pattern prefix.
• Derive O(L) insert and O(branching^wildcards) worst-case search time from how many times each element or state is visited.
• Test the boundary explicitly: A wildcard matches exactly one character, and a match must end at a terminal node.

Browse the searchable 100 LeetCode Python Solutions hub. Previous: 208. Implement Trie (Prefix Tree) · Next: 212. Word Search II