Decode Ways

Problem

A message made of capital letters was encoded by replacing each letter with its position in the alphabet: A became 1, B became 2, ..., Z became 26, and the digits were concatenated with no separators. You are given the resulting digit string s. Count how many different letter strings could have produced it. A group of digits is only valid if it is 1–9 or 10–26 with no leading zero; 0, 06, and 27 are not valid codes. Return 0 if no decoding exists.

• s is a digit string up to about a hundred characters long, and it may start with a 0.
• The answer is guaranteed to fit in a normal signed integer.

Examples

• s = "21" → 2. Read as 2,1 (BA) or 21 (U).
• s = "119" → 3. 1,1,9 (AAI), 11,9 (KI), and 1,19 (AS).
• s = "07" → 0. A zero cannot start a code, and 07 is not the same code as 7.

Hints

1. Look at the last one or two digits of the string. Each valid decoding ends by consuming either one digit or two.
2. If you knew the number of decodings of every shorter prefix, how would you combine two of them to get the count for the full string?
3. This is a 1D DP over prefixes with the Fibonacci-like transition count[i] = (count[i-1] if last digit valid) + (count[i-2] if last two digits valid).