一条包含字母 A-Z 的消息通过以下的方式进行了编码：

'A' -> 1
'B' -> 2
...
'Z' -> 26
要 解码 一条已编码的消息，所有的数字都必须分组，然后按原来的编码方案反向映射回字母（可能存在多种方式）。例如，"11106" 可以映射为：

"AAJF" 对应分组 (1 1 10 6)
"KJF" 对应分组 (11 10 6)
注意，像 (1 11 06) 这样的分组是无效的，因为 "06" 不可以映射为 'F' ，因为 "6" 与 "06" 不同。

除了 上面描述的数字字母映射方案，编码消息中可能包含 '' 字符，可以表示从 '1' 到 '9' 的任一数字（不包括 '0'）。例如，编码字符串 "1" 可以表示 "11"、"12"、"13"、"14"、"15"、"16"、"17"、"18" 或 "19" 中的任意一条消息。对 "1*" 进行解码，相当于解码该字符串可以表示的任何编码消息。

给你一个字符串 s ，由数字和 '*' 字符组成，返回 解码 该字符串的方法 数目 。

由于答案数目可能非常大，返回对 109 + 7 取余 的结果。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/decode-ways-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

import java.util.Scanner;

class Solution {

    private final int MOD = 1000000007;

    public int numDecodings(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        if (s.charAt(0) == '0') {
            return 0;
        }
        long a = 1;
        long b = s.charAt(0) == '*' ? 9 : 1;
        long c;
        for (int i = 1; i < s.length(); ++i) {
            if (s.charAt(i) == '*') {
                if (s.charAt(i - 1) == '0') {
                    c = b * 9 % MOD;
                } else if (s.charAt(i - 1) == '1') {
                    c = (a * 9 + b * 9) % MOD;
                } else if (s.charAt(i - 1) == '2') {
                    c = (a * 6 + b * 9) % MOD;
                } else if (s.charAt(i - 1) == '*') {
                    c = (a * 15 + b * 9) % MOD;
                } else {
                    c = b * 9 % MOD;
                }
            } else if (s.charAt(i) == '0') {
                if (s.charAt(i - 1) == '1' || s.charAt(i - 1) == '2') {
                    c = a;
                } else if (s.charAt(i - 1) == '*') {
                    c = 2 * a;
                } else {
                    c = 0;
                }
            } else {
                if (s.charAt(i - 1) == '0') {
                    c = b;
                } else if (s.charAt(i - 1) == '1') {
                    c = (a + b) % MOD;
                } else if (s.charAt(i - 1) == '2') {
                    if (s.charAt(i) >= '1' && s.charAt(i) <= '6') {
                        c = (a + b) % MOD;
                    } else {
                        c = b;
                    }
                } else if (s.charAt(i - 1) == '*') {
                    if (s.charAt(i) >= '1' && s.charAt(i) <= '6') {
                        c = (a * 2 + b) % MOD;
                    } else {
                        c = (a + b) % MOD;
                    }
                } else {
                    c = b;
                }
            }
            if (c == 0) {
                return 0;
            }
            a = b;
            b = c;
        }

        return (int) b;
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNext()) {
            System.out.println(new Solution().numDecodings(in.next()));
        }
    }
}