Tries
Wildcard walk
Why it matters
Crossword helpers, command palettes, and dictionary tools often accept a pattern with unknown letters. A hash lookup cannot resolve a wildcard, while comparing the pattern with every stored word becomes slow as the dictionary grows. Search must honor each "." without scanning words whose prefixes cannot match.
Example
Design Add and Search Words
A word dictionary supporting addWord and search. In search, '.' matches any letter. Tests call wordDictionary(ops, args).
- Input
- operations = ["WordDictionary", "addWord", "addWord", "addWord", "search", "search", "search", "search"], arguments = [[], ["bad"], ["dad"], ["mad"], ["pad"], ["bad"], [".ad"], ["b.."]]
- Output
- [None, None, None, None, False, True, True, True]
Approach 2 · Resolve the bottleneck
The idea
Keep one example in view
Design Add and Search Words
operations = ["WordDictionary", "addWord", "addWord", "addWord", "search", "search", "search", "search"], arguments = [[], ["bad"], ["dad"], ["mad"], ["pad"], ["bad"], [".ad"], ["b.."]]→[None, None, None, None, False, True, True, True]
The baseline, Compare against every word, is O(n · k) · O(n · k). The better model below keeps this exact input and removes that bottleneck.
With "bad", "dad", and "mad" stored, a brute list may scan words until one matches ".ad", and a miss scans all three. In the trie, fixed letters follow one edge and the dot branches only among b, d, and m; the first full marked path returns True.
After adding "bad", "dad", and "mad", the root has b, d, and m children. search("pad") fails immediately because p is absent. search("bad") follows b → a → d and succeeds only because d carries an end mark.
For search(".ad"), dfs at position 0 tries root children; the b branch reaches the marked word "bad" and short-circuits True. For "b..", the first b is fixed, then each dot tries the current node's children until b → a → d reaches a mark.
Pro
The rest of this is on Pro
The idea above is free. The walkthrough, the cost, and the practice are on Pro.