639. Decode Ways II (Hard)

A message containing letters fromA-Zis being encoded to numbers using the following mapping way:

'A' -> 1
'B' -> 2
...
'Z' -> 26

Beyond that, now the encoded string can also contain the character '*', which can be treated as one of the numbers from 1 to 9.

Given the encoded message containing digits and the character '*', return the total number of ways to decode it.

Also, since the answer may be very large, you should return the output mod 10^9+ 7.

Example 1:

Input: "*"
Output: 9
Explanation: The encoded message can be decoded to the string: "A", "B", "C", "D", "E", "F", "G", "H", "I".

Example 2:

Input: "1*"
Output: 9 + 9 = 18

Note:

1. The length of the input string will fit in range [1, 10^5].
2. The input string will only contain the character '*' and digits '0' - '9'.

Solution 1: DP O(n); O(n)

    public int numDecodings(String s) {
        if (s == null || s.length() == 0 || s.charAt(0) == '0') {
            return 0;
        }
        //long array is better than int array
        int n = s.length();
        long[] dp = new long[n + 1];
        dp[0] = 1;
        dp[1] = (s.charAt(0) == '*') ? 9 : 1;
        for (int i = 2; i <= n; i++) {
            char first = s.charAt(i - 2);
            char second = s.charAt(i - 1);

            // For dp[i-1], s.charAt(i - 1) is decoded as one char.
            if (second == '*') {
                dp[i] += 9 * dp[i - 1]; //*不是+，比如前面有10种方式，那么总共是90种。
            } else if (second > '0') {
                dp[i] += dp[i - 1]; //second只有1种方式，直接加即可，相当于*1。
            }

            // For dp[i-2], the last two digits are decoded as one char.
            // at first, consider the first char and then the second
            if (first == '*') {
                if (second == '*') { //两个**,只有11到26且不包括20，所以乘15。
                    dp[i] += 15 * dp[i - 2];
                } else if (second <= '6') { //1second and 2second
                    dp[i] += 2 * dp[i - 2];
                } else { //second > 6
                    dp[i] += dp[i - 2];
                }
            } else if (first == '1' || first == '2') {
                if (second == '*') {
                    if (first == '1') {
                        dp[i] += 9 * dp[i - 2];
                    } else { // first == '2'
                        dp[i] += 6 * dp[i - 2];
                    }
                } else if (((first - '0') * 10 + (second - '0')) <= 26) {
                    dp[i] += dp[i - 2];
                }
            }

            dp[i] %= 1000000007;
        }

        return (int) dp[n];
    }

Solution 2: DP O(n); O(1) 面试不要直接写这个，傻逼才直接写

    public int numDecodings(String s) {
        long mod = (long) Math.pow(10, 9) + 7; //Math.pow() return double, so must use explicit type conversion
        long endingAny = 1, ending1 = 0, ending2 = 0;
        for (char c : s.toCharArray()) {
            long curEndingAny = 0;
            if (c == '*') {
                curEndingAny = 9 * endingAny + 9 * ending1 + 6 * ending2;
                ending1 = endingAny;
                ending2 = endingAny;
            } else {
                curEndingAny = (c == '0' ? 0 : endingAny) + ending1 + (c <= '6' ? ending2 : 0);
                ending1 = (c == '1' ? endingAny : 0);
                ending2 = (c == '2' ? endingAny : 0);
            }
            endingAny = curEndingAny % mod;
        }
        return (int) endingAny;
    }

Follow Up:

1.*符号可以代表0~9之间任意一个数字，而不是1~9。

    /**
     * 小变种：*可以表示0-9
     * 只需修改*的部分代码即可，改3个数字，17,3,10
     */
    public int numDecodings(String s) {
        if (s == null || s.length() == 0 || s.charAt(0) == '0') {
            return 0;
        }
        //long array is better than int array
        int n = s.length();
        long[] dp = new long[n + 1];
        dp[0] = 1;
        dp[1] = (s.charAt(0) == '*') ? 9 : 1; //首位的*不能表示0
        for (int i = 2; i <= n; i++) {
            char first = s.charAt(i - 2);
            char second = s.charAt(i - 1);

            // For dp[i-1], s.charAt(i - 1) is decoded as one char.
            if (second == '*') {
                dp[i] += 9 * dp[i - 1]; //*不是+，比如前面有10种方式，那么总共是90种。不能表示0
            } else if (second > '0') {
                dp[i] += dp[i - 1]; //second只有1种方式，直接加即可，相当于*1。
            }

            // For dp[i-2], the last two digits are decoded as one char.
            // at first, consider the first char and then the second
            if (first == '*') {
                if (second == '*') { //两个**,只有10到26，所以乘17。注意：如果第一个*表示0，和只用second是一样的，所以不能算0
                    dp[i] += 17 * dp[i - 2];
                } else if (second <= '6') { //1second and 2second
                    dp[i] += 2 * dp[i - 2];
                } else { //second > 6
                    dp[i] += dp[i - 2];
                }
            } else if (first == '1' || first == '2') {
                if (second == '*') {
                    if (first == '1') { //0-9，10种
                        dp[i] += 10 * dp[i - 2];
                    } else { // first == '2'，0-6,7种
                        dp[i] += 7 * dp[i - 2];
                    }
                } else if (((first - '0') * 10 + (second - '0')) <= 26) {
                    dp[i] += dp[i - 2];
                }
            }

            dp[i] %= 1000000007;
        }

        return (int) dp[n];
    }