Decode Ways
The problem
A digit string encodes letters with 1 → A through 26 → Z. Count valid decodings. A zero cannot stand alone, and codes cannot begin with zero. The input is nonempty.
Example
"121" → 3 (ABA, AU, LA); "06" → 0
Need a hint?
The final letter uses either one valid digit or two valid digits.
Write pseudocode, trace the example, or note an edge case. This scratchpad does not run code.
Notes stay in this browser when storage is available.
Read the solution approach
Set the empty-prefix count to one. For each prefix, add the previous count when its last digit is not zero. Also add the count two positions back when the last two digits form 10 through 26. Keep two previous counts; invalid zeros naturally give zero ways.
Complexity
O(n) time and O(1) auxiliary space.
Before moving on, explain why the algorithm is correct and trace a boundary case without looking at the approach.