The problem
Design a structure with addWord(word) and search(word), where the search word may contain dots, and a dot matches any one letter.
Input: add bad, add dad, add mad, search pad, search bad, search .ad, search b.. Output: false, true, true, true
Picture it
Same letter tree as a trie. For a normal letter we follow that one branch. When we meet a dot, we don’t know which letter is meant, so we try every branch at that point; if any of them leads to a complete word, the search succeeds.
How to recognise it
- You store words and search with a pattern where some positions are fixed letters and some are wildcards.
- Fixed letters narrow the candidates one position at a time, which is exactly how a walk down a trie works.
- A wildcard means "try every child here", so the walk becomes a depth-first search (DFS) that branches only at wildcards.
- LeetCode allows up to 10^4 calls, words of up to 25 letters, and at most 2 dots per search, which keeps the branching small.
Start with brute force
Keep a list of words. For a search, compare the pattern with every stored word of the same length, letting . match anything.
class WordDictionaryBrute:
def __init__(self):
self.words = []
def add_word(self, word):
self.words.append(word)
def search(self, word):
return any(len(w) == len(word) and
all(p == "." or p == c for p, c in zip(word, w))
for w in self.words)
Adding is O(1), but each search is O(N · L) for N words of length L. With 5,000 adds followed by 5,000 searches that miss, that is up to 5,000 × 5,000 × 25 ≈ 6 × 10^8 character comparisons.
From brute force to the idea
- Find the waste. A search for
badcompares againstdadandmadtoo, even though the first letter already rules them out. - Store words in a trie.
add_wordis the same as a trie insert: walk withsetdefault, then mark the end with"$". - Search recursively by position.
search(word, node, i)asks: canword[i:]be matched starting atnode? The first call uses the root and position 0. - A letter follows one branch. If
word[i]is a letter, the answer isword[i] in nodeand a match of the rest from that child. A missing letter fails at once. - A dot tries every branch. If
word[i]is".", try every child except the"$"marker, and succeed ifanyof them matches the rest.anystops at the first success. - At the end, check the marker. When
i == len(word), the pattern matched a path; it is a stored word only if"$"is in the node.
This is the key idea: letters walk straight down the trie, and only a dot branches out to all children.
The key idea
Trie + depth-first search: branch over all children on “.”. Plain letters stay O(length).
Python solution
class WordDictionary:
def __init__(self):
self.root = {}
def add_word(self, word):
node = self.root
for ch in word:
node = node.setdefault(ch, {})
node["$"] = True
def search(self, word, node=None, i=0):
node = self.root if node is None else node
if i == len(word):
return "$" in node
if word[i] == ".": # try every branch
return any(self.search(word, kid, i + 1)
for ch, kid in node.items() if ch != "$")
return word[i] in node and self.search(word, node[word[i]], i + 1)In the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.
Complexity
| Approach | Time | Space |
|---|---|---|
| Brute force | add O(1); search O(N · L): every stored word is compared | O(total characters) |
| Trie + DFS (shown code) | add O(L); search O(L) with no dots, up to O(26^d · L) with d dots (at most 676 paths for 2 dots) | O(total characters) for the trie, plus O(L) recursion depth |
With no limit on dots, a pattern of all dots can visit every node of the trie, so the worst case is O(size of the trie).
Edge cases
- The example: after adding
bad,dad,mad:padisFalse,bad,.adandb..areTrue. - All dots (
...): matches any stored 3-letter word,True;....isFalsebecause no word has four letters. - Pattern shorter than every word (
b): the walk ends on a node without"$", soFalse. - Empty pattern:
Falseunless the empty word was added, which marks the root. - Recursion depth: at most one call per letter, so 26 frames for a 25-letter word; far below Python's limit.
Common mistakes
- Iterating over every key including
"$"at a dot. The valueTrueis then passed as a node, and the next step raisesTypeError(argument of type 'bool' is not iterable). - Returning after the first child at a dot instead of trying all of them, so
.adfails when the first child is abwith noadbelow it. - Forgetting the end marker check, so
b..matches a storedbade's prefix path. - Copying the remaining pattern with slices (
word[1:]) at every step, which adds O(L) work per call; passing the indexiavoids it.
Add count(word): how many distinct stored words match the pattern. After adding bad, dad, mad, bed (and bad again), count(".ad") is 3 and count("b.d") is 2. Describe your approach, then write it if you like.
Compare with our answer
Use the same DFS, but return numbers instead of booleans. A dot now has to sum the counts of all children, because every branch may contribute matches; any would stop too early. A word added twice still has one end marker, so it is counted once.
class WordCounter(WordDictionary):
def count(self, word, node=None, i=0):
node = self.root if node is None else node
if i == len(word):
return 1 if "$" in node else 0
if word[i] == ".":
return sum(self.count(word, kid, i + 1)
for ch, kid in node.items() if ch != "$")
if word[i] not in node:
return 0
return self.count(word, node[word[i]], i + 1)
count("...") is 4. The cost is the same as the worst case of search, since nothing can stop early.
A strong answer mentions: replacing any with sum, why duplicates count once, and that counting cannot short-circuit.
1. A crossword helper stores a dictionary and answers patterns like c.t or ..ane, where a dot is any letter. Which approach fits best?
Letters cut the search down to a single branch, and only dots fan out. A set cannot match wildcards, binary search only handles a fixed prefix (useless for ..ane), and comparing with every word is O(N · L).
2. Why can a search with no dots run in O(L) regardless of how many words are stored?
Without dots, there is never a choice of branch: each step is one dictionary lookup. The number of stored words only affects how big the trie is, not how many nodes one path visits.
3. A learner removes if ch != "$" from the dot branch. After adding b and ba, which search now crashes?
The b node holds "$": True before its a child, so the dot first tries True as a node and "$" in True raises TypeError. The other searches either have no dot or use it at the root, which has no marker.
Score 60% or more and the lesson is marked complete.