LeetCode 211 - Design Add and Search Words Data Structure

This Medium design problem combines ordinary Trie lookup with wildcard search. Adding a word follows one path through the Trie. Searching becomes a DFS when a dot can match any lowercase letter, because the search may need to continue through every child at that depth.

---

Problem link and explanation

• Problem: 211. Design Add and Search Words Data Structure
• Summary: Implement a WordDictionary that stores words through addWord and checks complete matches through search. A . in a query matches any single lowercase letter.

Each node stores 26 child positions and an is_end flag. The flag distinguishes a stored word from a prefix that happens to exist in the Trie.

---

Approach

addWord maps each character to an array index. It creates a node when the path does not exist, moves to that child, and marks the final node as the end of a word.

for ch in word:
    idx = ord(ch) - ord('a')
    if not cur.children[idx]:
        cur.children[idx] = TrieNode()
    cur = cur.children[idx]

cur.is_end = True

The search DFS carries the current node and character depth. A regular character follows one child. A dot tries every child and returns as soon as one branch matches the remaining suffix.

if ch == '.':
    for child in node.children:
        if self.dfs(child, depth + 1, word):
            return True

Reaching the end of the query is not enough by itself. If only app was inserted, the path for ap exists, but ap should still return false. The base case therefore returns node.is_end.

---

Complexity analysis

• Add word: For a word of length L, insertion takes O(L) time and up to O(L) new Trie nodes.
• Search: Without wildcards, lookup takes O(L) time. Dots introduce branching across as many as 26 children, so a wildcard-heavy query may visit many nodes in the matching portion of the Trie. The recursion stack uses O(L) space.
• Stored data: Total Trie space is proportional to the number of nodes created by all inserted words.

---

Implementation code

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

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

    def addWord(self, word: str) -> None:
        cur = self.root

        for ch in word:
            idx = ord(ch) - ord('a')
            if not cur.children[idx]:
                cur.children[idx] = TrieNode()
            cur = cur.children[idx]

        cur.is_end = True

    def dfs(self, node, depth, word) -> bool:
        if not node:
            return False
        if len(word) == depth:
            return node.is_end

        ch = word[depth]
        if ch == '.':
            for child in node.children:
                if self.dfs(child, depth + 1, word):
                    return True
        else:
            idx = ord(ch) - ord('a')
            next_node = node.children[idx]
            if next_node and self.dfs(next_node, depth + 1, word):
                return True

        return False

    def search(self, word: str) -> bool:
        return self.dfs(self.root, 0, word)

---

Summary and reflection

A standard Trie lookup follows one path, but one wildcard turns the operation into a search tree. That transition is the main point of the problem: the storage structure stays the same while the query semantics change the traversal algorithm. The is_end flag is equally important because a valid prefix is not necessarily a stored word.