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 Suggestion Oracle.
Checking every full spell makes each keystroke feel slow.
How you win
- 1Recognize when Trie autocomplete matches the clues
- 2Keep this true after every move: every enumerated node extends the requested prefix and results remain in lexicographic order
- 3Reach the result within O(prefix length + characters explored for k results)
Rules and pressure
- Target cost: O(prefix length + characters explored for k results)
- State rule: every enumerated node extends the requested prefix and results remain in lexicographic order
Lesson 1 of 3
Live algorithm trace
Trie autocomplete
Complete execution1 of 6
mobile
word
mouse
moneypot
monitor
mousepad
Build one trie containing all five catalog words.
1
build a trie with word markers2
walk the requested prefix3
return empty if the path is missing4
dfs children in sorted order5
emit at word markers6
stop after k suggestionswords = 5sharedPrefix = mo
Truth to preserve / Cost target
Truth to preserve
every enumerated node extends the requested prefix and results remain in lexicographic order
Cost target
O(prefix length + characters explored for k results)
Autocomplete first walks the fixed prefix. From that node, depth-first traversal in sorted child order emits matching words lexicographically and can stop as soon as k suggestions are collected.
Your call · What should guide every step of this algorithm?