题目
A message containing letters from A-Z is 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:
The length of the input string will fit in range [1, 105].
The input string will only contain the character '*' and digits '0' - '9'.

答案

class Solution {
    public int numDecodings(String s) {
        long[] dp = new long[s.length() + 1];
        long first, second;

        // Base case
        dp[s.length()] = 1;

        if(s.charAt(s.length() - 1) == '0')
            dp[s.length() - 1] = 0;
        else if(s.charAt(s.length() - 1) == '*')
            dp[s.length() - 1] = 9;
        else
            dp[s.length() - 1] = 1;


        for(int i = s.length() - 2; i >= 0; i--) {
            // Look at ith character

            if(s.charAt(i) == '*') {
                first = 9 * dp[i + 1];
            }
            else {
                int n = Integer.parseInt(s.substring(i, i+1));
                first = (n > 0) ? dp[i + 1] : 0;
            }
            if(s.charAt(i) == '*' && s.charAt(i+1) != '*') {
                if(s.charAt(i+1) <= '6') second = 2 * dp[i + 2];
                else second = dp[i + 2];
            }
            else if(s.charAt(i) != '*' && s.charAt(i+1) == '*') {
                if(s.charAt(i) == '0' || s.charAt(i) > '2') second = 0;
                else second = (s.charAt(i) == '1') ? 9 * dp[i + 2] : 6 * dp[i + 2];
            }
            else if(s.charAt(i) != '*' && s.charAt(i+1) != '*') {
                int n = Integer.parseInt(s.substring(i, i+2));
                second = (n > 0 && n <= 26 && s.charAt(i) != '0') ? second = dp[i + 2] : 0;
            }
            else {
                second = 15 * dp[i + 2];
            }

            dp[i] = (first + second) % 1000000007;
        }
        return (int)dp[0];
    }
}