Decode Ways II

hard dp string

Problem

Decode a digit string where '*' is a wildcard for 1..9. Return number of decodings mod 10^9+7.

Inputs = '1*'

Output18

9 ways for '1*' + 9 ways for '1' alone — equals 18.

input

def num_decodings(s):
    MOD = 10**9 + 7
    def one(c): return 9 if c == '*' else (0 if c == '0' else 1)
    def two(a, b):
        if a == '*' and b == '*': return 15
        if a == '*': return 2 if b <= '6' else 1
        if b == '*': return 9 if a == '1' else 6 if a == '2' else 0
        v = int(a + b); return 1 if 10 <= v <= 26 else 0
    n = len(s); dp = [0] * (n + 1); dp[0] = 1; dp[1] = one(s[0])
    for i in range(2, n + 1):
        dp[i] = (dp[i-1] * one(s[i-1]) + dp[i-2] * two(s[i-2], s[i-1])) % MOD
    return dp[n]

function numDecodings(s) {
  const MOD = 1000000007n;
  const one = c => c === '*' ? 9n : (c === '0' ? 0n : 1n);
  const two = (a, b) => {
    if (a === '*' && b === '*') return 15n;
    if (a === '*') return b <= '6' ? 2n : 1n;
    if (b === '*') return a === '1' ? 9n : a === '2' ? 6n : 0n;
    const v = +(a + b); return v >= 10 && v <= 26 ? 1n : 0n;
  };
  let a = 1n, b = one(s[0]);
  for (let i = 1; i < s.length; i++) {
    const c = (b * one(s[i]) + a * two(s[i-1], s[i])) % MOD;
    a = b; b = c;
  }
  return Number(b);
}

int numDecodings(String s) {
    long MOD = 1_000_000_007L; int n = s.length();
    long[] dp = new long[n + 1]; dp[0] = 1;
    dp[1] = one(s.charAt(0));
    for (int i = 2; i <= n; i++) dp[i] = (dp[i-1] * one(s.charAt(i-1)) + dp[i-2] * two(s.charAt(i-2), s.charAt(i-1))) % MOD;
    return (int) dp[n];
}
long one(char c) { return c == '*' ? 9 : (c == '0' ? 0 : 1); }
long two(char a, char b) {
    if (a == '*' && b == '*') return 15;
    if (a == '*') return b <= '6' ? 2 : 1;
    if (b == '*') return a == '1' ? 9 : a == '2' ? 6 : 0;
    int v = (a - '0') * 10 + (b - '0'); return v >= 10 && v <= 26 ? 1 : 0;
}

long MOD = 1e9 + 7;
long one(char c) { return c == '*' ? 9 : (c == '0' ? 0 : 1); }
long two(char a, char b) {
    if (a == '*' && b == '*') return 15;
    if (a == '*') return b <= '6' ? 2 : 1;
    if (b == '*') return a == '1' ? 9 : a == '2' ? 6 : 0;
    int v = (a - '0') * 10 + (b - '0'); return v >= 10 && v <= 26 ? 1 : 0;
}
int numDecodings(string s) {
    int n = s.size(); vector dp(n + 1); dp[0] = 1; dp[1] = one(s[0]);
    for (int i = 2; i <= n; i++) dp[i] = (dp[i-1] * one(s[i-1]) + dp[i-2] * two(s[i-2], s[i-1])) % MOD;
    return (int) dp[n];
}

Explanation

This is the wildcard version of decoding: the digit '*' can stand for any digit 1 to 9. We still build the answer left to right with a 1D DP, where dp[i] is the number of ways to decode the first i characters.

The trick is to count how many letters a single character can become, and how many valid two-digit codes a pair can become. The helper one(c) returns those counts for one character (a normal digit is 1 way, '0' is 0, and '*' is 9). The helper two(a, b) returns how many of the values 10..26 the pair ab can represent.

Then the recurrence is just dp[i] = dp[i-1]·one(s[i-1]) + dp[i-2]·two(s[i-2], s[i-1]): take every way to decode up to the previous char and extend it by one letter, plus every way up to two chars back and extend it by a two-digit letter.

Example: s = "1*". The single '*' alone gives one('*') = 9 letters, and the pair "1*" means 10..19, which is two('1','*') = 9 letters. So dp[2] = 1·9 + 1·9 = 18.

The careful part is enumerating each (prev, cur) wildcard case correctly; once those small counts are right, the DP itself is a single linear pass.

Time: O(n) Space: O(n)