639. Decode Ways II

一个典型的String dp
难点是各种case比较多，需要逐步分析
总的来说transfer function和dp[i - 1] 以及dp[i - 2]都有关
慢慢写就好了
一个bug点是 '*'不能代表0，所以'**' 只能表示[11,19][21,26]
Time O(n)
Space O(n)
-> Space 可以优化到O(1)因为只涉及了 dp[i] dp[i - 1] dp[i - 2] 三个state


75.73 %

class Solution {
    public int numDecodings(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        long mod = (long)(1e9 + 7);
        int star = '*' - '0';
        // dp[i] -> total num of ways to decode substring[0, i)
        long[] dp = new long[s.length() + 1];
        dp[0] = 1l;
       
        for (int i = 1; i < s.length() + 1; i++) {
            int curr = s.charAt(i - 1) - '0';
            // curr can be a choice?
            if (curr == star) {
                dp[i] += dp[i - 1] * 9;
            } else if (curr > 0) {
                dp[i] += dp[i - 1];
            }
           
            if (i > 1) {
                int prev = s.charAt(i - 2) - '0';
                if (prev == star) {
                    if (curr == star) { // ** -> [11,19][21,26]
                        dp[i] += dp[i - 2] * (19 - 11 + 1 + 26 - 21 + 1);
                    } else if (curr < 7) { // 1curr / 2curr
                        dp[i] += dp[i - 2] * 2;
                    } else {
                        dp[i] += dp[i - 2]; // 1curr
                    }
                } else if (prev == 1) {
                    if (curr == star) { // 1* -> [11, 19]
                        dp[i] += dp[i - 2] * (19 - 11 + 1);
                    } else {
                        dp[i] += dp[i - 2]; // 1curr
                    }
                } else if (prev == 2) {
                    if (curr == star) {
                        dp[i] += dp[i - 2] * (26 - 21 + 1);
                    } else if (curr < 7) {
                        dp[i] += dp[i - 2];
                    }
                }
            }
            dp[i] = dp[i] % mod;
        }
        return (int)dp[s.length()];
    }
}