Add and Search Words with Wildcards

The plain trie walk works because each character tells you exactly which edge to follow. A wildcard breaks that: at a . there is no single edge, so you must try them all. This problem tests whether you can see that the walk has become a search — and whether you can say what that search costs.

The problem

Design a word dictionary with two operations:

• add_word(word) — store a word of lowercase letters.
• search(pattern) — return True if some stored word matches the pattern. The pattern has lowercase letters and ., where . matches exactly one letter of any kind.

Example. Add cat, car, cart and dog. Then:

• search("c.t") → True. cat matches: c, any letter, t.
• search(".og") → True. dog matches.
• search("....") → True. cart has four letters.
• search(".a") → False. No stored word has two letters.
• search("d..s") → False. No four-letter word starts with d and ends with s.

Constraints. Words and patterns are 1 to 25 characters. There are up to 10^4 calls. A pattern has at most 3 dots.

Clarifying questions

• Does . match exactly one character, or any run of characters? Exactly one. A pattern only matches words of the same length.
• Can a word contain .? No; only patterns can.
• Can words be added after searches? Yes, the calls are mixed.
• Should search return the word or just True/False? Just True/False.

Approach 1: the simple way

Keep a list of words. For a search, compare the pattern with every word of the same length, letter by letter, treating . as a match.

1class WordListDictionary:2    """Brute force: compare the pattern with every stored word."""34    def __init__(self) -> None:5        self.words: list[str] = []67    def add_word(self, word: str) -> None:8        self.words.append(word)910    def search(self, pattern: str) -> bool:11        for w in self.words:12            if len(w) == len(pattern) and all(13                p == "." or p == c for p, c in zip(pattern, w)14            ):15                return True16        return False

Each search costs O(n × L) for n stored words of length up to L. With 5,000 words added and 5,000 searches of 25 characters, that is up to 5,000 × 5,000 × 25 ≈ 6 × 10^8 character comparisons — and it scans every word even when the pattern's first letter rules almost all of them out. Grouping words by length helps a little, but a pattern like c.... still reads every five-letter word.

The key insight

In a trie, a letter in the pattern picks exactly one child. A . picks all children, because any letter is allowed. So the search is a depth-first search over the trie, driven by the pattern: at a letter, follow one edge; at a dot, try each edge in turn and succeed if any branch succeeds.

Letters still do what they did in the plain trie — they cut away every word that does not match, without looking at it. Only the dots cause branching, and a branch dies the moment it reaches a node without the next required letter.

Approach 2: a trie with DFS at wildcards

1class WordDictionary:2    """Trie where '.' in a search pattern matches any one character."""34    def __init__(self) -> None:5        self.root = TrieNode()67    def add_word(self, word: str) -> None:8        node = self.root9        for ch in word:10            node = node.children.setdefault(ch, TrieNode())11        node.is_word = True1213    def search(self, pattern: str) -> bool:14        def dfs(node: TrieNode, i: int) -> bool:15            if i == len(pattern):16                return node.is_word17            ch = pattern[i]18            if ch == ".":19                return any(dfs(child, i + 1) for child in node.children.values())20            child = node.children.get(ch)21            return child is not None and dfs(child, i + 1)2223        return dfs(self.root, 0)

Step by step:

1. add_word is the ordinary trie insert, using the TrieNode class from the core-idea lesson. setdefault creates the child if it is missing and returns it either way.
2. dfs(node, i) asks: starting from node, can the rest of the pattern, from index i, be matched?
3. End of pattern: the answer is the node's flag. Reaching a node is not enough — a word must end there.
4. A dot: try every child. any stops at the first child that succeeds.
5. A letter: follow that one edge if it exists; otherwise this branch fails.

Dry run of search(".og") on the trie holding cat, car, cart and dog. The root's children are c and d, in insertion order.

The c branch died after one lookup. The words under it — cat, car, cart — were never read letter by letter.

Complexity. add_word is O(L). For search, a pattern with no dots is O(L), the plain walk. With w dots, each dot can multiply the branches by up to 26, so the number of paths explored is at most 26^w, each up to L long: O(26^w × L).

There is a second, often tighter, bound: within one search, each trie node is visited at most once. A node sits at exactly one depth, and at that depth the DFS is always at the same pattern index, so no node is reached twice. The cost is therefore also at most O(N), where N is the number of trie nodes. The real cost is O(min(26^w × L, N)). Space is O(L) for the recursion, plus O(S) for the trie itself.

With at most 3 dots, 26^3 × 25 ≈ 440,000 steps is the worst case for one search, and real tries prune most of it.

Edge cases

• All dots ("....") → explores every node at depth 4 or less; succeeds if any four-letter word exists. This is the worst case — say so.
• Pattern longer than any word → every branch dies at a missing edge.
• A dot at the last position ("ca.") → tries each child of node a and checks its flag: r ends car, so True.
• Matching a prefix, not a word ("ca") → the walk reaches node a but its flag is not set: False.

Follow-ups

• "Most searches have a dot in the first position." Keep a separate trie per word length, or store each word reversed in a second trie and search the reversed pattern when its last letter is fixed. Either cuts the early branching.
• "* matches any run of letters, including none." At a *, try two moves: skip the star (dfs(node, i + 1)), or consume one letter and stay on the star (dfs(child, i) for each child). Add memoisation on (node, i), because a node can now be reached at different pattern indexes.
• "Count the matching words instead of True/False." Replace any with a sum, and add 1 at the end of the pattern when the flag is set.