• 1 <= word.length <= 25
• word in addWord consists of lowercase English letters only
• pattern in search consists of lowercase English letters and '.'
• At most 10⁴ calls in total to addWord and search
• A pattern may consist entirely of dots

This is a dictionary with one added ability, and the interesting question is what that ability costs. Without wildcards, storing words in a trie makes every lookup a single walk down one path. The dot is what turns that walk into a search.

Keep the words in a list. For each query, compare against every word, position by position, treating a dot as matching whatever is there.

def search(pattern):
    for word in words:
        if len(word) != len(pattern):
            continue
        if all(p == '.' or p == c for p, c in zip(pattern, word)):
            return True
    return False

Correct, and O(N × L) per query. With 10⁴ operations over a growing dictionary that becomes slow, but the shape of the waste matters more than the number.

Suppose the dictionary holds "bad", "bat" and "bag", and the pattern is "ba.". The loop compares b against b, then a against a — and then does it again for the second word, and again for the third. Three words sharing a prefix cause the same prefix to be re-verified once per word. The list has no idea those words have anything in common.

A trie fixes exactly that. Store each word as a route through a tree, one edge per character, where a node represents the prefix spelled by the route reaching it. Words sharing a prefix share the nodes for it, so "bad", "bat" and "bag" store b and a once between them and branch only at the last character. Each node carries a flag recording whether a stored word ends there — necessary because a node may exist merely as part of a longer word.

Now an exact pattern is a single walk: follow one edge per character, and on arrival check the flag. O(L), with no dependence on how many words are stored, and the shared prefix is verified once rather than once per word.

Here is the crux. At each step of the walk you are standing on a node and reading a pattern character, and that character determines your choice.

If it is a letter, there is exactly one legal move: the child on that edge. If no such child exists, this route is dead. One option, no decision.

If it is a dot, it matches any letter, so every existing child is a legal move. Now there is a genuine branching decision, and no way to know in advance which branch leads to a match.

That converts a walk into a search over a tree of possibilities. And when a problem requires trying options, and abandoning one to try another when it fails, the tool is depth-first search with backtracking — commit to a branch, follow it as far as it goes, and on failure return and try the next.

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_word = False

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

    def addWord(self, word):
        node = self.root
        for ch in word:
            if ch not in node.children:
                node.children[ch] = TrieNode()
            node = node.children[ch]
        node.is_word = True                 # set AFTER the loop, on the last node only

    def search(self, pattern):
        def match(node, i):
            if i == len(pattern):
                return node.is_word         # consumed the pattern: is this a real word?
            ch = pattern[i]
            if ch == '.':
                for child in node.children.values():
                    if match(child, i + 1):
                        return True         # any branch succeeding is enough
                return False                # every branch failed
            if ch not in node.children:
                return False                # dead end
            return match(node.children[ch], i + 1)

        return match(self.root, 0)

With no dots, the search follows one path: O(L).

With dots, each one multiplies the branches. The upper bound is O(26^L), since each of L positions could fan out 26 ways — but that bound is loose in a way worth explaining, because it is what an interviewer is listening for.

The recursion can only visit nodes that actually exist in the trie. A dot does not try 26 possibilities; it tries however many children that node really has, often one or two. So the true cost is bounded by the number of trie nodes reachable within L levels, which for a realistic dictionary is far below 26^L. The pathological case needs both a dense dictionary and a pattern of all dots.

Position matters too, and it is worth noticing. In "b..", the first character is fixed, so the search commits to a single branch immediately and only fans out inside that subtree. In "..b", the fan-out starts at the root and every branch of the whole dictionary is explored. Same number of dots, very different work — leading wildcards are the expensive ones.

Dictionary: "bad", "dad", "mad". The trie has three separate branches from the root — b, d and m — each leading through a to d, and each final d flagged as a word. Note "ad" is stored three times over, once per branch, since the words share a suffix rather than a prefix and a trie only exploits shared beginnings.

search(".ad").
- At the root with i = 0, the character is a dot, so every child is tried: b, d, m in turn.
- Try the b branch, i = 1. The character is now 'a', a letter, so exactly one move is legal. The b node has an a child, so step into it, i = 2.
- Character 'd', a letter. The a node under b has a d child, so step in, i = 3.
- The pattern is consumed. Check the flag on this node: it is set, because "bad" was added. Return true, which propagates straight up and the d and m branches are never examined at all.

search("..").
- At the root, a dot, so try the b branch with i = 1.
- Another dot. The b node's only child is a, so recurse into it with i = 2.
- The pattern is consumed. Check the flag on the "ba" node — it is false, since "ba" was never added, only "bad". Return false.
- Back at the b node, no other children remain, so that branch fails. The same happens under d and m.
- Every branch exhausted: return false. Correct, since a two-dot pattern only matches two-letter words and there are none. The length check was enforced automatically by the structure rather than by any explicit comparison.

search("b..").
- At the root, the character 'b' is a letter, so only the b branch is considered — the d and m branches are eliminated before any wildcard work happens.
- Dot at i = 1: try the only child, a. Dot at i = 2: try the only child, d. Pattern consumed, flag is set. Return true.

Compare the first and third traces: both have two wildcard positions, but the leading dot in ".ad" forced consideration of three root branches while the leading letter in "b.." forced only one.

The transferable idea is a small one, and it generalises well beyond tries: a query with an unknown in it turns a lookup into a search. When each query character determines a unique move, you walk. When one character permits several moves, you must try them all, and trying-then-abandoning is depth-first search with backtracking.

That framing recurs constantly. Pattern matching with wildcards, regular expressions against a text, solving a crossword against a dictionary, matching IP addresses against routing rules with wildcard octets — all are a structure walk that becomes a branching search wherever the query is underspecified.

The recognition signal is the combination: a set of strings queried by structure rather than by exact value, with some part of the query unspecified. The trie handles the sharing; the recursion handles the ambiguity.

Train the reflex: build the structure so the common case is a single walk, then let the ambiguous case branch. Do not design for the wildcard first — design for the walk, and let recursion turn it into a search only where it must.