639 Decode Ways II

639. Decode Ways II

1. Question

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 109+ 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'.

2. Implementation

(1) DP

class Solution {
    long MOD = (long)1e9 + 7;
    public int numDecodings(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        long[] dp = new long[2];
        dp[0] = ways(s.charAt(0));

        if (s.length() == 1) {
            return (int)dp[0];
        }

        dp[1] = dp[0] * ways(s.charAt(1)) + ways(s.charAt(0), s.charAt(1));
        for (int i = 2; i < s.length(); i++) {
            long temp = dp[1];
            dp[1] = (dp[1] * ways(s.charAt(i)) + dp[0] * ways(s.charAt(i - 1), s.charAt(i))) % MOD;
            dp[0] = temp;
        }
        return (int)dp[1];
    }

    public int ways(char c1) {
        if (c1 == '0') {
            return 0;
        }
        else if (c1 == '*') {
            return 9;
        }
        else {
            return 1;
        }
    }

    public int ways(char c1, char c2) {
        String num = "" + c1 + "" + c2;

        if (c1 != '*' && c2 != '*') {
            if (Integer.parseInt(num) >= 10 && Integer.parseInt(num) <= 26) {
                return 1;
            }
        }
        else if (c1 == '*' && c2 == '*') {
            return 15;
        }
        else if (c1 == '*') {
            if (c2 >= '0' && c2 <= '6') {
                return 2;
            }
            else {
                return 1;
            }
        }
        else {
            if (c1 == '1') {
                return 9;
            }
            else if (c1 == '2') {
                return 6;
            }
        }
        return 0;
    }
}

3. Time & Space Complexity

时间复杂度O(n), 空间复杂度O(1)