Decode Ways

Problem

A string consisting of uppercase english characters can be encoded to a number using the following mapping:

'A' -> "1"
'B' -> "2"
...
'Z' -> "26"

To decode a message, digits must be grouped and then mapped back into letters using the reverse of the mapping above. There may be multiple ways to decode a message. For example, "1012" can be mapped into:

• "JAB" with the grouping (10 1 2)
• "JL" with the grouping (10 12)

The grouping (1 01 2) is invalid because 01 cannot be mapped into a letter since it contains a leading zero.

Given a string s containing only digits, return the number of ways to decode it. You can assume that the answer fits in a 32-bit integer.

Examples

Example 1:

Input: s = "12"

Output: 2

Explanation: "12" could be decoded as "AB" (1 2) or "L" (12).

Example 2:

Input: s = "01"

Output: 0

Explanation: “01” cannot be decoded because “01” cannot be mapped into a letter.

Constraints

• 1 <= s.length <= 100
• s consists of digits

You should aim for a solution as good or better than O(n) time and O(n) space, where n is the length of the given string.

Solution

class Solution {
public:
    // At each index i, count all valid decodings that end at s[i].
    // A decoding can end in two possible ways:
    //
    // 1. Use s[i] as a single digit.
    //    If s[i] is not '0', then every decoding up to i - 1 can be extended
    //    with this digit, so add prev.
    //
    // 2. Use s[i - 1] and s[i] as a two-digit number.
    //    If the pair is between 10 and 26, then every decoding up to i - 2
    //    can be extended with this pair, so add prev_prev.
    //
    // These two cases cover all possible endings, so cur is their sum.
    int numDecodings(const string &s) {
        int prev_prev = 1;
        int prev = s[0] == '0' ? 0 : 1;
        int cur = prev;
        for (int i = 1; i < s.size(); ++i) {
            cur = 0;
            if (s[i] != '0') {
                cur += prev;
            }
            if (s[i - 1] == '1' || 
                (s[i - 1] == '2' && s[i] <= '6')
            ) {
                cur += prev_prev;
            }
 
            prev_prev = prev;
            prev = cur;
        }
        return cur;
    }
};