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 Root Garden.
Checking every full spell makes each keystroke feel slow.
How you win
- 1Recognize when Shortest-prefix replacement matches the clues
- 2Keep this true after every move: the current path is a prefix of the original word, and the first end marker is its shortest dictionary root
- 3Reach the result within O(total dictionary and sentence characters)
Rules and pressure
- Target cost: O(total dictionary and sentence characters)
- State rule: the current path is a prefix of the original word, and the first end marker is its shortest dictionary root
Lesson 1 of 3
Live algorithm trace
Shortest-prefix replacement
Complete execution1 of 6
cat
root
bat
rat
the
cattle
was
rattled
Insert cat, bat, and rat as marked trie paths before scanning the sentence words.
1
insert every root into a trie2
for each sentence word3
walk its characters from the root4
stop at the first word marker5
use the root or keep the original6
join replacementsroots = 3firstLetters = c, b, r
Truth to preserve / Cost target
Truth to preserve
the current path is a prefix of the original word, and the first end marker is its shortest dictionary root
Cost target
O(total dictionary and sentence characters)
Insert dictionary roots into a trie. For each sentence word, stop at the first end marker while walking its characters because that is the shortest root that can replace it.
Your call · What should guide every step of this algorithm?