Problem context and objectives
Mission briefing
Rune decoder · Thousands of spells share the same opening symbols
Reuse shared prefixes to complete the requested spell: The Wildcard Vault.
Checking every full spell makes each keystroke feel slow.
How you win
- 1Recognize when Trie wildcard DFS matches the clues
- 2Keep this true after every move: each DFS state represents one trie node after matching exactly pattern[0:index]
- 3Reach the result within O(branches explored times pattern length)
Rules and pressure
- Target cost: O(branches explored times pattern length)
- State rule: each DFS state represents one trie node after matching exactly pattern[0:index]
Lesson 1 of 3
Live algorithm trace
Trie wildcard DFS
Complete execution1 of 6
bad
dad
mad
.ad
pattern
Build three first-letter branches for bad, dad, and mad.
1
build a trie of words2
dfs(node, index)3
if index == length: return node.isWord4
if pattern[index] is literal: follow one child5
if dot: try every child6
return whether any branch matchesroots = b, d, mpattern = .ad
Truth to preserve / Cost target
Truth to preserve
each DFS state represents one trie node after matching exactly pattern[0:index]
Cost target
O(branches explored times pattern length)
Literal characters follow one trie edge. A dot wildcard must try every child, but each branch still advances exactly one pattern position and succeeds only at a marked word ending.
Your call · What should guide every step of this algorithm?