Problem context and objectives
Mission briefing
Energy-route planner · A runner crosses a line of power stations
Build each decision from smaller outcomes already solved: The Message Decoder.
Re-solving the same future branches drains exponential energy.
How you win
- 1Recognize when Decode ways matches the clues
- 2Keep this true after every move: ways[i] counts all valid decodings of the first i digits
- 3Reach the result within O(n) time and O(1) space
Rules and pressure
- Target cost: O(n) time and O(1) space
- State rule: ways[i] counts all valid decodings of the first i digits
Lesson 1 of 3
Live algorithm trace
Decode ways
Complete execution1 of 5
Seed the empty prefix and the first valid digit.
1
empty prefix has one decoding2
for each next digit3
add previous ways if digit is 1 through 94
add two-back ways if pair is 10 through 265
shift the two counts6
return final counttwoBack = 1oneBack = 1
Truth to preserve / Cost target
Truth to preserve
ways[i] counts all valid decodings of the first i digits
Cost target
O(n) time and O(1) space
A prefix can end with a valid one-digit letter or a valid 10-through-26 pair. Add the counts from those predecessor prefixes.
Your call · What should guide every step of this algorithm?