Decode Ways II

Java

class Solution {
    //             1*3
    //     1(*)3  (1*)3 1(*3)
    //   
    public int numDecodings(String s) {
        if (s == null || s.length() == 0 || s.charAt(0) == '0') {
            return 0;
        }
        int len = s.length();
        long mod = (long)1e9 + 7;
        long[] dp = new long[len + 1];
        dp[0] = 1;
        dp[1] = s.charAt(0) == '*' ? 9 : 1;
        // [1, 9, 9 + 2]
        for (int i = 1; i < len; i++) {
            char first = s.charAt(i - 1);
            char second = s.charAt(i);
            // As one digit value
            if (second == '*') { // *
                dp[i + 1] += dp[i] * 9;
            } else if (second != '0') { // 1 - 9
                dp[i + 1] += dp[i];
            }
            
            // As two digit values
            if (first == '*') {
                if (second == '*') { // **
                    dp[i + 1] += dp[i - 1] * 15;
                } else if (second <= '6') { // *6
                    dp[i + 1] += 2 * dp[i - 1];
                } else { // * can only be one
                    dp[i + 1] += dp[i - 1];
                }
            } else if (second == '*' && first == '1'){ // 1*
                dp[i + 1] += dp[i - 1] * 9;
            } else if (second == '*' && first == '2') { // 2*
                dp[i + 1] += dp[i - 1] * 6;
            } else if (first == '1' || (first == '2' && second <= '6')) { // no star, 10 ~ 26
                dp[i + 1] += dp[i - 1];
            }
            
            dp[i + 1] %= mod;
        }
        return (int)dp[len];
    }
}