TL;DR
Trie plus a DFS that fans out on '.': addWord is O(L); search is O(L) with no dots and O(26^d · L) with d dots (d ≤ 2 here); space is O(total characters added).
Approach 1 — Brute force (bucket words by length, scan on search)
Store the words in lists keyed by length; a search scans every stored word of the right length and compares character by character, letting '.' match anything.
from collections import defaultdict
class WordDictionary:
def __init__(self) -> None:
self.by_len: dict[int, list[str]] = defaultdict(list)
def addWord(self, word: str) -> None:
self.by_len[len(word)].append(word)
def search(self, word: str) -> bool:
candidates = self.by_len.get(len(word), [])
return any(
all(q == "." or q == c for q, c in zip(word, w))
for w in candidates
)
addWord is O(1); search is O(N · L) over the N stored words of that length. With up to 10^4 total calls and L up to 25, an adversarial mix (5·10^3 adds, then 5·10^3 searches) costs about 5·10^3 · 5·10^3 · 25 ≈ 6·10^8 character comparisons — over the line in Python, and it shares no work between words with common prefixes.
Approach 2 — Trie + recursive DFS (the intended solution)
In a trie, a literal character selects exactly one child edge to follow; a '.' matches any letter, so the search must try every child. The single-path trie walk becomes a depth-first search that branches only at dots and stays a straight walk everywhere else. Because the trie merges words by shared prefix, a dot explores at most one subtree per distinct next letter, not one per stored word.
class TrieNode:
__slots__ = ("children", "is_end")
def __init__(self) -> None:
self.children: dict[str, "TrieNode"] = {}
self.is_end: bool = False
class WordDictionary:
def __init__(self) -> None:
self.root = TrieNode()
def addWord(self, word: str) -> None:
node = self.root
for ch in word:
if ch not in node.children:
node.children[ch] = TrieNode()
node = node.children[ch]
node.is_end = True
def search(self, word: str) -> bool:
def dfs(node: TrieNode, i: int) -> bool:
if i == len(word):
return node.is_end
ch = word[i]
if ch == ".":
return any(
dfs(child, i + 1)
for child in node.children.values()
)
nxt = node.children.get(ch)
return nxt is not None and dfs(nxt, i + 1)
return dfs(self.root, 0)
Walkthrough of the example. After addWord("bad"), addWord("dad"), addWord("mad"), the root has three children b, d, m, each leading through a to a d node with is_end = True.
flowchart TD
root((root))
root --> b((b))
root --> d((d))
root --> m((m))
b --> ba((a))
d --> da((a))
m --> ma((a))
ba --> bad([d end])
da --> dad([d end])
ma --> mad([d end])
Now search(".ad"): word[0] is '.', so the DFS tries all three root children. Branch b: word[1] = 'a' matches its child, word[2] = 'd' matches the next child, and at i == 3 the node has is_end = True, so the whole search returns True (short-circuiting the d and m branches). For search(".."): both dots match, for example b then a, but at i == 2 the a node has is_end = False and no branch reaches an end-of-word at depth 2, so the result is False. Length must match exactly.
Complexity: addWord is O(L). A dot-free search is a plain walk, O(L). Each '.' multiplies the branching by at most 26, so a query with d dots costs O(26^d · L); with the problem’s cap of d ≤ 2 that is O(676 · L) ≈ O(L) — and it is also bounded above by the total number of trie nodes, O(sum of added word lengths). Space is O(total characters added).
Approach 3 — Trie + iterative DFS (explicit stack)
The same branching search can run on an explicit stack of (node, i) states, which is worth knowing when an interviewer asks you to avoid recursion. L is at most 25, so Python’s recursion limit is never a real concern here, but the conversion is mechanical.
class TrieNode:
__slots__ = ("children", "is_end")
def __init__(self) -> None:
self.children: dict[str, "TrieNode"] = {}
self.is_end: bool = False
class WordDictionary:
def __init__(self) -> None:
self.root = TrieNode()
def addWord(self, word: str) -> None:
node = self.root
for ch in word:
if ch not in node.children:
node.children[ch] = TrieNode()
node = node.children[ch]
node.is_end = True
def search(self, word: str) -> bool:
stack: list[tuple[TrieNode, int]] = [(self.root, 0)]
while stack:
node, i = stack.pop()
if i == len(word):
if node.is_end:
return True
continue
ch = word[i]
if ch == ".":
for child in node.children.values():
stack.append((child, i + 1))
elif ch in node.children:
stack.append((node.children[ch], i + 1))
return False
Identical complexity to Approach 2: O(26^d · L) time per search, O(total characters) space, plus an O(states) stack during a query.
Common pitfalls
- Treating
'.' as “zero or more characters” (regex .* thinking) — it matches exactly one letter, so query length must equal word length.
- Returning
node.is_end too early: at a '.', succeeding just because some child exists instead of recursing into it — the remaining suffix still has to match.
- Forgetting the
i == len(word) base case must check is_end; without it, search("ba") would succeed after adding only "bad".
- In the brute force, skipping the length filter — comparing a query against words of a different length wastes time and, with careless
zip, silently accepts prefixes (zip stops at the shorter string).
Pattern takeaway
When a trie query contains uncertainty (a wildcard, an edit budget, a character class), the fix is the same: keep the plain walk for known characters and fan out over all children at the uncertain ones, so the branching is confined to the uncertain positions. The trie’s prefix-sharing keeps that fan-out cheap, because you branch per distinct letter rather than per stored word.