276. Decode Ways II

dp[i] = number of ways to decode the first i characters. Extend by either a single character (how many letters it could be) or a pair with the previous character (how many valid 10-26 codes that pair forms). '*' multiplies the counts because it stands for any of 1-9.

The DP

Let dp[i] be the number of ways to decode the prefix s[0..i-1]. There are two ways to extend to position i:

• Single character s[i-1]: contributes dp[i-1] * ones(s[i-1]), where ones(c) counts how many letters that one character can be.
• Two characters s[i-2] s[i-1]: contributes dp[i-2] * tens(s[i-2], s[i-1]), where tens(a, b) counts valid two-digit codes in 10..26.

dp[i] = dp[i-1]*ones(s[i-1]) + dp[i-2]*tens(s[i-2], s[i-1])   (mod 1e9+7)

The count helpers

• ones(c): '*' → 9 (any of 1-9); '0' → 0; any other digit → 1.
• tens(a, b) — number of pairs in [10, 26]:
  • a='1': b='*' → 9 (11-19), else 1.
  • a='2': b='*' → 6 (21-26), b<='6' → 1, else 0.
  • a='*': b='*' → 15 (11-19 and 21-26); b<='6' → 2 (1b and 2b); else → 1 (only 1b).
  • otherwise → 0.

Base: dp[0] = 1, dp[1] = ones(s[0]).

Worked example

s = "1*".

• dp[0] = 1, dp[1] = ones('1') = 1.
• dp[2] = dp[1]*ones('*') + dp[0]*tens('1','*') = 1*9 + 1*9 = 18.

The * alone gives 9 letters, and 1* as a pair gives 11-19 (another 9), total 18.

Complexity

• Time: O(n).
• Space: O(n) (reducible to O(1) with two rolling values).

class Solution {
    private static final int MOD = 1_000_000_007;

    public int numDecodingsII(String s) {
        int n = s.length();
        long[] dp = new long[n + 1];
        dp[0] = 1;
        dp[1] = ones(s.charAt(0));
        for (int i = 2; i <= n; i++) {
            dp[i] = (dp[i - 1] * ones(s.charAt(i - 1))
                     + dp[i - 2] * tens(s.charAt(i - 2), s.charAt(i - 1))) % MOD;
        }
        return (int) dp[n];
    }

    private int ones(char c) {
        if (c == '*') return 9;
        return c == '0' ? 0 : 1;
    }

    private int tens(char a, char b) {
        if (a == '*' && b == '*') return 15;
        if (a == '*') return b <= '6' ? 2 : 1;
        if (a == '1') return b == '*' ? 9 : 1;
        if (a == '2') {
            if (b == '*') return 6;
            return b <= '6' ? 1 : 0;
        }
        return 0;
    }
}