Lintcode 676. Decode Ways II

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 10^9 + 7.

Example

Example 1

Input: "*"
Output: 9
Explanation: You can change it to "A", "B", "C", "D", "E", "F", "G", "H", "I".

Example 2

Input: "1*"
Output: 18

Notice

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.

Code (Java):

public class Solution {
    /**
     * @param s: a message being encoded
     * @return: an integer
     */
    public int numDecodings(String s) {
        // write your code here
        if (s == null || s.length() == 0) {
            return 0;
        }
        
        if (s.charAt(0) == '0') {
            return 0;
        } 
        
        long MOD = (long)1e9 + 7;
        
        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 c = s.charAt(i - 1);
            
            // regular case
            if (c != '*') {
                if (c != '0') {
                    dp[i] = dp[i - 1];
                }
                
                int numCombinations = getNumberOfValidNumbers(s.charAt(i - 2), s.charAt(i - 1));
                dp[i] += dp[i - 2] * numCombinations % MOD;
            } else {
                dp[i] = dp[i - 1] * 9 % MOD; // * match 1-9
                int numCombinations = getNumberOfValidNumbers(s.charAt(i - 2), s.charAt(i - 1));
                dp[i] += dp[i - 2] * numCombinations % MOD;
                
            }
        }
        
        return (int)(dp[n] % MOD);
    }
    
    private int getNumberOfValidNumbers(char a, char b) {
        // 4 cases:
        // * *
        // * num
        // num *
        // num num
        
        int ans = 0;
        
        if (a == '*' && b == '*') {
            ans = 15; // 11 -> 26, not 10, 20
        } else if (a == '*') {
            int nb = Character.getNumericValue(b);
            if (nb >= 0 && nb <= 6) {
                ans = 2; // 1* and 21->26
            } else {
                ans = 1; // 1*
            }
        } else if (b == '*') {
            int na = Character.getNumericValue(a);
            if (na == 1) {
                ans = 9; // 11-19
            } else if (na == 2) {
                ans = 6; // 21-26
            } else {
                ans = 0;
            }
        } else {
            int na = Character.getNumericValue(a);
            int nb = Character.getNumericValue(b);
            int num = na * 10 + nb;
            
            if (na == 0) {
                ans = 0;
            } else if (num >= 1 && num <= 26) {
                ans = 1;
            }
        }
        
        return ans;
    }
}