Digit DP: Decoding and Pattern Matching

Decode Ways (LeetCode 91)

A message containing letters from A-Z is encoded to numbers using: 'A' -> 1, 'B' -> 2, ..., 'Z' -> 26. Given a numeric string, return the total ways to decode it.

public int numDecodings(String s) {
    int n = s.length();
    int[] dp = new int[n + 1];
    dp[0] = 1; // Base case: one way to decode an empty string
    dp[1] = s.charAt(0) == '0' ? 0 : 1;
    
    for (int i = 2; i <= n; i++) {
        // Individual digit decoding
        int one = Integer.parseInt(s.substring(i - 1, i));
        if (one >= 1) dp[i] += dp[i - 1];
        
        // Two-digit decoding
        int two = Integer.parseInt(s.substring(i - 2, i));
        if (two >= 10 && two <= 26) dp[i] += dp[i - 2];
    }
    return dp[n];
}

Decode Ways II (LeetCode 639)

Includes a * wildcard that represents any digit from 1 to 9. Result should be modulo $10^9 + 7$.

public int numDecodings(String s) {
    int n = s.length();
    long MOD = 1_000_000_007;
    long[] dp = new long[n + 1];
    dp[0] = 1;
    dp[1] = s.charAt(0) == '*' ? 9 : (s.charAt(0) == '0' ? 0 : 1);
    
    for (int i = 2; i <= n; i++) {
        char cur = s.charAt(i - 1), prev = s.charAt(i - 2);
        
        // Case 1: Decode a single character s[i-1]
        if (cur == '*') dp[i] += 9 * dp[i - 1];
        else if (cur != '0') dp[i] += dp[i - 1];
        
        // Case 2: Decode pair s[i-2..i-1]
        if (prev == '*' && cur == '*') {
            // Combinations: 11-19 (9) + 21-26 (6) = 15 total
            dp[i] += 15 * dp[i - 2];
        } else if (prev == '*') {
            // if cur <= 6: '1'+cur or '2'+cur (2 ways); else only '1'+cur (1 way)
            dp[i] += (cur <= '6' ? 2 : 1) * dp[i - 2];
        } else if (cur == '*') {
            if (prev == '1') dp[i] += 9 * dp[i - 2]; // 11-19
            else if (prev == '2') dp[i] += 6 * dp[i - 2]; // 21-26
        } else {
            int two = (prev - '0') * 10 + (cur - '0');
            if (two >= 10 && two <= 26) dp[i] += dp[i - 2];
        }
        dp[i] %= MOD;
    }
    return (int) dp[n];
}

Distinct Subsequences (LeetCode 115)

Number of distinct subsequences of s which equals t.

public int numDistinct(String s, String t) {
    int m = s.length(), n = t.length();
    long[][] dp = new long[m + 1][n + 1];
    for (int i = 0; i <= m; i++) dp[i][0] = 1; // Empty 't' is always a match
    
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            dp[i][j] = dp[i - 1][j]; // Option 1: Ignore s[i-1]
            if (s.charAt(i - 1) == t.charAt(j - 1)) {
                dp[i][j] += dp[i - 1][j - 1]; // Option 2: Pair s[i-1] with t[j-1]
            }
        }
    }
    return (int) dp[m][n];
}

At a Glance Comparison Table