A message of letters was encoded by mapping A to "1", B to "2", ... Z to "26" and concatenating the digits. Given the digit string s, return how many different letter messages could have produced it. "12" could be "AB" (1,2) or "L" (12), so the answer is 2. A digit string with no valid decoding — a stray or leading zero — decodes zero ways.
Examples
Example 1:
Input: s = "12"
Output: 2
Example 2:
Input: s = "226"
Output: 3
Explanation: (2,2,6), (22,6), (2,26).
Example 3:
Input: s = "06"
Output: 0
Explanation: "06" is not a code — zero can only appear inside 10 or 20.
Example 4:
Input: s = "2101"
Output: 1
Explanation: (2,10,1) and nothing else.
Constraints
1 <= s.length <= 100
s contains only digits.
Prerequisites
Dynamic programming — being able to say, in one sentence, what a single cell of your table MEANS. Everything else follows from that sentence. Rolling variables: when a state only looks back one or two steps, the table collapses to a couple of numbers.
How to think about it
1. Count Paths, Mind the Zeros Optimal
Intuition
Decodings of the first i digits split by how the last letter was formed: one digit (valid unless it is a zero) or two (valid only for 10 through 26). Add the counts from those two positions and the recurrence is done. All the difficulty is zeros — a zero decodes to nothing alone and only survives inside 10 or 20 — which is exactly what the two conditions encode.
Algorithm
1. Start with one way to decode the empty prefix. 2. At each digit, add the previous count when the digit is not zero. 3. Add the count from two back when the two-digit number reads 10 to 26. 4. Roll the two counts forward.