Decode Ways
Decode Ways is a medium 1-D Dynamic Programming problem from the Blind 75. The key pattern is 1-d dynamic programming, and a good solution runs in O(n) time.
Problem
Count decodings of a digit string where 1 through 26 map to letters and zero cannot stand alone.
Examples
Example 1
Input
"1212"Output
5Example 2
Input
"27"Output
1Example 3
Input
"123"Output
3Approach
The decodings up to position i add the decodings up to i − 1 when the current digit is not 0, and up to i − 2 when the last two digits form 10–26.
| Pattern | 1-D dynamic programming |
|---|---|
| Time | O(n) |
| Space | O(1) |
Watch out for
A 0 can only be read as part of 10 or 20; a leading 0 makes the count 0.