Design Add and Search Words Data Structure

PracticeNeetCode ↗LeetCode ↗

Design a data structure that supports adding words and searching for a word, where a search pattern may contain . as a wildcard matching any single character.

Example

Key Pointers

• This is a trie, same shape as a standard prefix tree — addWord behaves exactly like trie insert.
• A . can match any character, so a plain iterative walk isn't enough: when the pattern hits a ., every child at that node needs to be tried.
• Only branch on . — a literal character still does a direct, O(1) child lookup, keeping the common case fast.

Step-by-Step Analysis

1. Build the same node/children/is_end structure as a normal trie.
2. Write a recursive helper dfs(node, i) that walks the search word starting from index i.
3. If the current character is a normal letter, look it up directly in node.children — missing means this path fails.
4. If the current character is ., recurse into every child of node — the search succeeds if any branch returns True.
5. Base case: once i reaches the end of the word, return the node's is_end flag.

Complexity

Time: O(L) with no wildcards, up to O(26^L) worst case when every character is a wildcard — Space: O(N · L) for the trie, O(L) recursion depth

Code

class TrieNode:
    def __init__(self):
        self.children: dict[str, "TrieNode"] = {}
        self.is_end = False


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

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

    def search(self, word: str) -> bool:
        def dfs(node: TrieNode, i: int) -> bool:
            if i == len(word):
                return node.is_end
            ch = word[i]
            if ch == ".":
                return any(dfs(child, i + 1) for child in node.children.values())
            if ch not in node.children:
                return False
            return dfs(node.children[ch], i + 1)

        return dfs(self.root, 0)

Code Explanation

How the solution above works, piece by piece.

1. addWord is a normal trie insert.
2. search runs dfs(node, i): "can word[i:] be matched starting from node?"
3. When i == len(word), the match succeeds only if this node ends a word.
4. A . matches any character: try every child with any(...), which stops at the first success.
5. A normal character follows its child or fails. Without dots it's O(L); with dots it can branch, up to O(26^dots · L) in the worst case.

Visual Walkthrough

Running the example calls:

Video Explanation

NeetCode — Design Add and Search Words Data Structure, LeetCode 211