Design Add and Search Words

Add and Search Words extends a plain dictionary with a wildcard: the search pattern may contain ., which matches any single letter. It is the classic problem that turns a trie into a recursive search — and shows why wildcards can blow up the cost.

The slow way first

The naive store is a list of words. addWord is easy, but search(".ad") then has to scan every stored word and compare it character by character against the pattern. With n words of length L that is O(n·L) per query — and it throws away the huge amount of structure that words share (bad, dad, mad all end in ad).

The question to ask: how do I share the common prefixes so I only walk the letters that actually exist? That structure is a trie.

The idea: a trie plus recursive search

A trie (prefix tree) stores words letter by letter. Each node has a map of children keyed by letter, plus an is_word flag marking where a complete word ends. Inserting bad, dad, mad creates three top-level children (b, d, m), each leading down to its own a then d.

Search walks the pattern character by character:

• A real letter follows exactly one child — if that child is missing, fail fast.
• A dot is a wildcard: we cannot pick one child, so we recurse into every child and succeed if any branch matches the rest of the pattern. That branching is a depth-first search.

The key insight: a normal letter prunes to a single path, but every . multiplies the branches we explore — so wildcards near the front of the pattern are the expensive ones.

Walk through it

Step through the animation. First we insert bad, dad, mad, building three root-to-leaf paths (green leaves are word ends). Then search("b..") runs: the b follows one child, and each . lights up the fan-out to every child of the current node. We land on the bad leaf, it is flagged is_word, so the search returns True.

Pseudocode

addWord(word):
    node = root
    for ch in word:
        if ch not a child of node: create it
        node = node.children[ch]
    node.is_word = True
 
search(word, node = root):
    for i, ch in word:
        if ch is a real letter:
            if ch not in node.children: return False
            node = node.children[ch]
        else:                                  # ch == "."
            return any(search(word[i+1:], child)
                       for child in node.children.values())
    return node.is_word

The Python solution

class WordDictionary:
    def __init__(self):
        self.children = {}
        self.is_word = False
 
    def addWord(self, word):
        node = self
        for ch in word:
            node = node.children.setdefault(ch, WordDictionary())
        node.is_word = True
 
    def search(self, word, node=None):
        node = node or self
        for i, ch in enumerate(word):
            if ch != ".":
                if ch not in node.children:
                    return False
                node = node.children[ch]
            else:
                return any(
                    self.search(word[i + 1:], child)
                    for child in node.children.values()
                )
        return node.is_word

• Each node IS a WordDictionary with a children dict and an is_word flag — the trie is just nodes pointing at nodes.
• setdefault in addWord creates a child node only when the letter is new, so shared prefixes share nodes.
• In search, a real letter advances to its single child (or fails fast if missing).
• The else branch is the wildcard: any(...) recurses into every child with the rest of the pattern (word[i + 1:]) and returns True if any branch matches.
• When the loop finishes, the answer is node.is_word — we matched the length, but only count it if a real word ends here.

Complexity

A pattern of all dots forces the search to explore every path of that length, so the worst case is exponential in the number of dots (O(26^L) for an alphabet of 26 letters). In practice most patterns have few dots, so the trie still prunes aggressively.

When this pattern shows up

Practice