leetcode-decode-ways-ii

发表于   |   分类于 ，   |  

题目大意

　　https://leetcode.com/problems/decode-ways-ii/#/description

　　Decode Ways 的加强版，增加了*，*能匹配1-9（注意不能匹配0），题目输入保证只含有*,`0-9。并对输出取模。

题目分析

　　跟Decode Ways一样，很容易看出来是DP，可以把*的情况分解成9种，然后用二维数组的第二维度代表1-9这9种情况，实际转移方程就是分情况讨论稍微麻烦了一点，具体可以看下代码。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
public class Solution {
    
    private final int MOD = 1000000007;
    
    public int numDecodings(String s) {
        if (s == null || s.equals("")) {
            return 0;
        }
        char[] c = s.toCharArray();
        int len = c.length;
        long[][] dp = new long[len + 1][10];
        // init
        if (c[len - 1] == '*') {
            Arrays.fill(dp[len - 1], 1);
        } else if (c[len - 1] != '0') {
            dp[len - 1][c[len - 1] - '0'] = 1;
        }
        // DP process
        for (int i = len - 2; i >= 0; i--) {
            if (c[i] == '0') {
                continue;
            }
            long ans2 = 0;
            if (i + 2 == len) {
                ans2 = 1;
            } else {
                for (int j = 1; j <= 9; j++) {
                    ans2 = (ans2 + dp[i + 2][j]) % MOD;
                }
            }
            long ans1 = 0;
            for (int j = 1; j <= 9; j++) {
                ans1 = (ans1 + dp[i + 1][j]) % MOD;
            }
           // ans1 和 ans2 是先把dp[i + 1]和dp[i + 2]预处理一下
            String str = s.substring(i, i + 2);            
            if (str.indexOf('*') < 0) {
                dp[i][c[i] - '0'] = Integer.valueOf(str) <= 26 ? (ans2 + ans1) % MOD : ans1;
            } else if (c[i] == '*' && c[i + 1] == '*') {
                dp[i][1] = (ans1 + ans2 * 9) % MOD;
                dp[i][2] = (ans1 + ans2 * 6) % MOD;
                dp[i][3] = dp[i][4] = dp[i][5] = dp[i][6] = dp[i][7] = dp[i][8] = dp[i][9] = ans1;
            } else if (c[i + 1] == '*') {
                if (c[i] == '1') {
                    dp[i][1] = (ans1 + ans2 * 9) % MOD;
                } else if (c[i] == '2') {
                    dp[i][2] = (ans1 + ans2 * 6) % MOD;
                } else {
                    dp[i][c[i] - '0'] = ans1;
                }
            } else {
                for (int j = 1; j <= 9; j++) {
                    dp[i][j] = ans1;
                }
                if (c[i + 1] <= '9') {
                    dp[i][1] = (dp[i][1] + ans2) % MOD;
                }
                if (c[i + 1] <= '6') {
                    dp[i][2] = (dp[i][2] + ans2) % MOD;
                }
            }
        }
        long ans = 0;
        for (int i = 1; i <= 9; i++) {
            ans = (ans + dp[0][i]) % MOD;
        }
        return (int)ans;
    }
}

　　时间和空间复杂度：O(n)