Implement Trie with one
wildcard added, and that wildcard is the whole problem. A trie search is a walk down a single path;
a . turns it into a search over all paths, so the lookup stops being a
loop and becomes a recursion — and the complexity stops being linear.
The problem
Design a structure supporting addWord(word) and search(word), where the
searched word may contain . matching any single character.
addWord("bad"); addWord("dad"); addWord("mad")
search("pad") -> false
search("bad") -> true
search(".ad") -> true matches bad, dad and mad
search("b..") -> true matches bad
search("...") -> true
search("....") -> false length must match exactlyA . matches exactly one character, never zero or many. So the searched word's length
is fixed, and "...." cannot match a three-letter word — worth confirming, because it is
the difference between this and a regex.
Why the loop becomes a recursion
Without wildcards, each character determines the next node: one path, O(L), no
choices. A . removes that determinism — every existing child could be the right one, and
you cannot tell which without trying.
search(".ad") at the root, try EVERY child:
b -> then "ad" must match ✓
d -> then "ad" must match ✓
m -> then "ad" must match ✓So the search is a DFS over the trie, branching at each dot. The trie is unchanged from problem
208; only the lookup differs, and addWord is identical.
Java
class WordDictionary {
private static class Node {
Node[] children = new Node[26];
boolean isWord;
}
private final Node root = new Node();
public void addWord(String word) {
Node node = root;
for (char c : word.toCharArray()) {
int i = c - 'a';
if (node.children[i] == null) node.children[i] = new Node();
node = node.children[i];
}
node.isWord = true;
}
public boolean search(String word) {
return search(word, 0, root);
}
private boolean search(String word, int index, Node node) {
if (node == null) return false;
if (index == word.length()) return node.isWord; // length matched exactly
char c = word.charAt(index);
if (c != '.') {
return search(word, index + 1, node.children[c - 'a']);
}
// A dot: any existing child could work, so try them all.
for (Node child : node.children) {
if (child != null && search(word, index + 1, child)) return true;
}
return false;
}
}The node == null check at the top means the caller never has to guard —
node.children[c - 'a'] is passed straight through even when the path breaks, and the
next call returns false. That is what keeps the non-wildcard branch to one line.
index == word.length() returns node.isWord, not true. The
path existing means a prefix matched; the flag is what makes it a word — the same
distinction problem 208 turns on.
The loop over children short-circuits on the first success. On ".ad" against a trie
of many words that matters, since most branches fail immediately at the next character.
Python
class WordDictionary:
def __init__(self):
self.children: dict[str, "WordDictionary"] = {}
self.is_word = False
def addWord(self, word: str) -> None:
node = self
for c in word:
node = node.children.setdefault(c, WordDictionary())
node.is_word = True
def search(self, word: str) -> bool:
def walk(index: int, node) -> bool:
if index == len(word):
return node.is_word
c = word[index]
if c != ".":
child = node.children.get(c)
return child is not None and walk(index + 1, child)
# A dot: any existing child could work.
return any(walk(index + 1, child) for child in node.children.values())
return walk(0, self)any() short-circuits, so the generator stops at the first branch that succeeds —
the same behaviour as the Java loop's early return, written as one expression.
Iterating node.children.values() visits only the children that exist. The Java
version iterates all 26 slots and skips nulls, which is the array-versus-map trade from problem 208
showing up again: fixed arrays are faster to index and slower to enumerate.
Complexity
| Operation | Time |
|---|---|
addWord | O(L) |
search, no dots | O(L) |
search, all dots | O(26^L) in the worst case |
The worst case is the honest number and it is worth stating rather than hiding. A search of
L dots visits every node at depth L, so the bound is the branching factor
raised to the number of dots.
In practice it is far better, because the trie only contains paths that were actually inserted —
the branching factor is the real fan-out, not 26. A dictionary of a few thousand words has very few
nodes with many children below the second level, which is why ".ad" is fast and
"...." on a huge trie is not.
LeetCode bounds the number of dots at 2 for exactly this reason. Noticing that constraint and saying what it protects against is the strongest thing you can say about the complexity.
Why a trie rather than a list of words
A list plus a regex is a legitimate answer and is O(n · L) per search — every stored
word tested. The trie is better when many words share prefixes, because one failed comparison prunes
an entire subtree at once.
It is worse when the words are short and unrelated, where the trie is mostly pointer overhead. As always with tries: the structure pays for itself in proportion to how much prefix the data shares.
The pattern
Branching on a wildcard is the same shape as
Regular Expression
Matching (10), where . does the same job and * adds a second dimension.
Word Search II (212) walks a grid against a trie and prunes with exactly this
"does this path exist?" test. Design Search Autocomplete System (642) adds ranking
on top of the same structure.
The recognition: a trie turns "which stored strings match?" from a scan into a traversal, and any wildcard turns that traversal from a walk into a search.
What the interviewer is checking
- That
addWordis unchanged from problem 208 and only search differs. - That a dot branches over all existing children.
- That the base case returns
isWord, nottrue. - That a dot matches exactly one character, so lengths must match.
- Searching before adding anything, and searching all dots.
- The
O(26^L)worst case, stated honestly. - Why the real branching factor is much smaller than 26.