211. Design Add and Search Words Data Structure

The moment a search key can contain a . that matches any letter, a plain hash set stops working — not because a pattern can’t be hashed, but because exact-key lookup can’t do wildcard matching against every stored word. This is where a trie earns its keep, and where the wildcard turns a straight walk into a small DFS. It’s a core member of the trie pattern, and the exact idea here scales straight up to the harder grid problems.

The problem

Build a WordDictionary class with two operations: addWord(word) stores a word, and search(word) returns true if some stored word matches. The twist is that a search string can contain ., and a dot matches any single letter. (Full statement on LeetCode.)

Add bad, dad, mad. Then search("mad") is true, search(".ad") is true (the dot covers b, d, or m), and search("b..") is true — but search("pad") is false, since no stored word starts with p.

Intuition: a trie makes the dot a branch, not a barrier

If every search were a literal word, a HashSet<String> would be enough. The dot breaks that: .ad isn’t a key you can look up, it’s a shape you have to match against many keys at once. So you need a structure that shares letter-by-letter prefixes, and that’s a trie — each node holds up to 26 children, one per letter, and a flag marking where a real word ends.

Now the wildcard falls out naturally. Walking a literal character means stepping into exactly one child. Hitting a . means you don’t know which child, so you try all of them and succeed if any branch does. That “try one vs. try all” split is the whole problem, and it’s why search becomes a depth-first traversal instead of a single downward path:

$\text{match}(node, i) = \begin{cases} node.\text{isEnd} & i = \text{len} \\ \text{match}(node.child[c], i{+}1) & \text{word}[i] = c \\ \bigvee_{k} \text{match}(node.child[k], i{+}1) & \text{word}[i] = \text{'.'} \end{cases}$

A literal path costs one step per character. A dot fans out by up to 26, so $d$ dots can cost up to $26^d$ paths — bounded here because the constraints cap a query at 2 dots.

Solution

addWord is an ordinary trie insert: follow or create a child per letter, then mark the last node as a word end. search delegates to a recursive helper that carries the current node and index.

class WordDictionary {

    // 26 children (a–z) plus a flag for "a word ends here"
    private static class Node {
        Node[] next = new Node[26];
        boolean isEnd = false;
    }

    private final Node root = new Node();

    public void addWord(String word) {
        Node node = root;
        for (char c : word.toCharArray()) {
            int k = c - 'a';
            if (node.next[k] == null) node.next[k] = new Node();
            node = node.next[k];
        }
        node.isEnd = true;                 // only real words get this flag
    }

    public boolean search(String word) {
        return dfs(word, 0, root);
    }

    private boolean dfs(String word, int i, Node node) {
        if (node == null) return false;    // walked off the trie
        if (i == word.length()) return node.isEnd;  // matched fully? must be a word end

        char c = word.charAt(i);
        if (c == '.') {
            // wildcard: any existing child can carry the match
            for (Node child : node.next) {
                if (dfs(word, i + 1, child)) return true;
            }
            return false;
        }
        // literal: descend into exactly the one matching child
        return dfs(word, i + 1, node.next[c - 'a']);
    }
}

The i == word.length() check returning node.isEnd (not just true) is the line people miss: reaching the end of the pattern only counts if a word actually terminates there. Otherwise search("ba") would wrongly match after inserting only bad.

Complexity

Let $n$ be the word length and $d$ the number of dots in a query.

Operation	Time	Space
addWord	$O(n)$	$O(n)$ per new word
search (no dots)	$O(n)$	$O(n)$ recursion depth
search (d dots)	$O(26^d \cdot n)$ worst case	$O(n)$

Space across the whole structure is $O(\text{total characters stored})$, since shared prefixes collapse into shared nodes.

In an interview

Say the constraint out loud first: “a search can be a wildcard pattern, so a set won’t do — I need a trie because it lets one dot branch into all 26 children.” That framing shows you picked the structure for a reason, not by reflex. Then write the insert, and write search as a DFS from the start rather than trying to bolt wildcards onto an iterative loop later — the recursion handles the branch-and-backtrack for free.

The trap to name before they ask: the base case returns isEnd, not true. A leading dot is the other thing worth mentioning, since it forces a fan-out from the root immediately, which is why unbounded dots would blow up. This builds directly on the plain Implement Trie — add the wildcard DFS and you’re here — and the same recursive-DFS-over-a-trie idea is the engine behind Word Search II. The trie pattern hub ties the family together.

References

• LeetCode 211 — Design Add and Search Words Data Structure