Wildcard Search
Support '.' as a wildcard matching any character. During search, when you encounter '.', try ALL children and continue matching. If any path succeeds, the word matches. Uses DFS with branching at wildcards.
How It Works
Wildcard search extends trie lookup to patterns containing '.', which matches any single character. The search proceeds as a DFS over (trie node, pattern index) states: a literal character follows its single child pointer as usual, while a '.' branches into every existing child and recurses on each. The pattern matches if any branch consumes the whole pattern and lands on an end-of-word node.
Literal-only queries remain O(L). Each wildcard multiplies the frontier by up to the alphabet size, so a pattern of length L with w dots costs O(26^w * L) in the worst case — still far better than checking the pattern against every stored word, because shared prefixes collapse the branching and dead paths are pruned the moment a literal character finds no child. This dictionary-plus-pattern setup is exactly the Design Add and Search Words problem.
Step-by-Step Visualization
Code
static boolean searchWithWildcard(Trie trie, String word) {
return dfs(trie.root, word, 0);
}
static boolean dfs(TrieNode node, String word, int i) {
if (i == word.length()) return node.isEnd;
if (word.charAt(i) == '.') {
for (TrieNode child : node.children.values())
if (dfs(child, word, i + 1)) return true;
return false;
}
if (!node.children.containsKey(word.charAt(i))) return false;
return dfs(node.children.get(word.charAt(i)), word, i + 1);
}Tips & Gotchas
Practice Problems
- 1Design Add and Search Words Data Structure
- 2Prefix and Suffix Search
- 3Word Search II
About the Advanced Trie Pattern
Extend the basic trie to handle wildcards, combine with DFS for grid search, or store binary representations of numbers for XOR optimization.
Use a trie when you need prefix-based operations that hash maps can't do efficiently — like 'find all words starting with X' or 'find word matching pattern with wildcards'.
Common Trie Interview Problems
- Implement Trie
- Word Search II
- Design Add and Search Words
- Replace Words
- Maximum XOR of Two Numbers
Frequently Asked Questions
Why does '.' force DFS instead of a simple pointer walk?
A literal character determines a unique child, but '.' is compatible with every child the node has, and different children may lead to different outcomes deeper in the pattern. Only trying each branch — with backtracking on failure — explores all candidate words; the trie's structure keeps that branching limited to characters that actually exist.
How bad can performance get with many wildcards, and can it be mitigated?
A pattern of all dots visits every node at the matching depth, degenerating toward the full trie size. Mitigations include storing per-node subtree word counts to prune empty regions, bucketing words by length so only same-length subtries are searched, or capping wildcard count per query as real systems do.