167. Design Add and Search Words Data Structure

Store words in a trie exactly as usual. The only twist is the search: a '.' can be any letter, so at a dot we can't follow a single edge — we must try every child and succeed if any branch matches the rest of the pattern. That branching turns search from a straight walk into a depth-first search over the trie.

Why a trie

We need to match a pattern against a whole set of words. A trie stores all the words as shared paths, so a search explores only the branches consistent with the pattern instead of testing words one by one. addWord is the standard trie insert: descend character by character, creating nodes as needed, and mark the final node as a word-end.

Search with wildcards

Search walks the pattern and the trie together, but the dot changes the walk into a branching depth-first search. Process the pattern index i against the current node:

1. Base case: if i == len(word), the match succeeds only if node is marked as a word-end (we've consumed the whole pattern and landed exactly on a stored word).
2. Normal letter c: if node has a child for c, recurse into it with i + 1; otherwise fail immediately.
3. Dot .: the wildcard matches any single letter, so try every child. If recursing into any child (with i + 1) succeeds, the whole search succeeds; if all fail, this branch fails.

The first two cases are the same single walk as an ordinary trie. Only the dot forks the search.

Algorithm

• addWord(word): node = root; for each c, descend/create; mark last node end.
• search(word) = dfs(root, 0) where:
  • dfs(node, i): if i == len(word) return node.isEnd.
  • let c = word[i]; if c == '.' return true if dfs(child, i+1) for any child; else if c in children return dfs(child_c, i+1); else return false.

Worked example

Add bad, dad, mad. Then:

For ".ad", the dot forks into three sub-searches; the very first (b → a → d) already succeeds, so we return true without needing the others.

Complexity

Let L be the pattern length and N the number of trie nodes.

• addWord: O(L).
• search: O(L) when there are no dots (a single walk). With dots, a wildcard can branch to up to 26 children per position, so the worst case is O(26^d · L) where d is the number of dots — bounded and small because the problem caps dots.
• Space: O(total characters added) for the trie, plus O(L) recursion depth.

class WordDictionary {
    private WordDictionary[] children = new WordDictionary[26];
    private boolean isEnd = false;

    public WordDictionary() {}

    public void addWord(String word) {
        WordDictionary node = this;
        for (char c : word.toCharArray()) {
            int i = c - 'a';
            if (node.children[i] == null) node.children[i] = new WordDictionary();
            node = node.children[i];
        }
        node.isEnd = true;
    }

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

    private boolean dfs(String word, int i, WordDictionary node) {
        if (node == null) return false;
        if (i == word.length()) return node.isEnd;
        char c = word.charAt(i);
        if (c == '.') {
            for (int k = 0; k < 26; k++) {
                if (node.children[k] != null && dfs(word, i + 1, node.children[k])) return true;
            }
            return false;
        }
        return dfs(word, i + 1, node.children[c - 'a']);
    }
}