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 Board of Whispers.
Checking every full spell makes each keystroke feel slow.
How you win
- 1Recognize when Trie-pruned board DFS matches the clues
- 2Keep this true after every move: the DFS path spells exactly the trie prefix at the current node and contains no repeated board cell
- 3Reach the result within O(rows times cols times 4 to the maximum word length) worst case
Rules and pressure
- Target cost: O(rows times cols times 4 to the maximum word length) worst case
- State rule: the DFS path spells exactly the trie prefix at the current node and contains no repeated board cell
Lesson 1 of 3
Live algorithm trace
Trie-pruned board DFS
Complete execution1 of 8
o
a
a
n
e
t
a
e
i
h
k
r
i
f
l
v
Build one trie that shares every candidate word prefix.
1
build one trie for all words2
start DFS at every board cell3
reject if the cell has no trie child4
record a word marker5
mark the cell visited6
explore four neighbors7
restore the cell8
return found wordswords = oath, pea, eat, rainrootEdges = o, p, e, r
Truth to preserve / Cost target
Truth to preserve
the DFS path spells exactly the trie prefix at the current node and contains no repeated board cell
Cost target
O(rows times cols times 4 to the maximum word length) worst case
Build one trie for all candidate words, then start DFS from every board cell. A missing trie edge rejects the entire path immediately, while visited marking prevents one cell from being reused in the same word.
Your call · What should guide every step of this algorithm?