How Many Ways to Decode
Letters were encoded as numbers, A to Z becoming 1 to 26, and the
numbers were then run together with no separator. Given the digit string, print
how many different letter strings could have produced it.
12 -> 2 AB (1 2) or L (12)
226 -> 3 BZ, VF, BBF
06 -> 0 no letter is encoded as 06
The count can be large, so it is guaranteed to fit in a signed 64-bit integer.
Read one digit at a time and the choice is local: the current digit either
stands alone, or joins the one before it. So with ways(i) counting the
decodings of the first i characters:
ways(i) = ways(i-1) if the digit at i-1 is not '0'
+ ways(i-2) if the two digits ending at i-1 form 10..26
That is the same shape as counting stairs, and it is why this is the first DP most people meet that is not obviously a staircase.
Zero is the entire difficulty. 0 is not a letter, so it can never stand
alone, and it is only ever valid as the second half of 10 or 20. Every
wrong solution to this problem is wrong about zero: 06 is 0, 100 is 0, and
10 is 1.