题目

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

分析

这一题是Decode Ways的升级版，在0-9的基础上增加了*表示可以替换成1-9之间的任意一个字符。这题也是用动态规划

e0 = current number of ways we could decode, ending on any number;
e1 = current number of ways we could decode, ending on an open 1;
e2 = current number of ways we could decode, ending on an open 2

设置e0,e1,e2分别表示到上一个数为止，以任意数(0-9)、1、2结尾的可能数是多少。
设置f0,f1,f2表示对应的这一轮的可能数
具体分析见代码

代码

    Say we see some character c. We want to calculate f0, f1, f2, the corresponding versions of e0, e1, e2 after parsing character c.

If c == '*', then the number of ways to finish in total is: we could put * as a single digit number (9*e0), or we could pair * as a 2 digit number 1* in 9*e1 ways, or we could pair * as a 2 digit number 2* in 6*e2 ways. The number of ways to finish with an open 1 (or 2) is just e0.

If c != '*', then the number of ways to finish in total is: we could put c as a single digit if it is not zero ((c>'0')*e0), or we could pair c with our open 1, or we could pair c with our open 2 if it is 6 or less ((c<='6')*e2). The number of ways to finish with an open 1 (or 2) is e0 iff c == '1' (or c == '2').

public int numDecodings(String s) {
    if(s.length() == 0) return 0;
    int mod = 1000000007;
    long e0 = 1, e1 = 0, e2 = 0;
    long f0 = 0, f1 = 0, f2 =0;
    
    for(char c : s.toCharArray()){
        if(c == '*'){
            f0 = 9 * e0 + 9 * e1 + 6 * e2;   
            f1 = e0;
            f2 = e0;
        }else{
            f0 = (c > '0' ? e0 : 0) + e1 + (c <= '6' ? e2 : 0);
            f1 = c == '1' ? e0 : 0;
            f2 = c == '2' ? e0 : 0;
        }
        e0 = f0 % mod;
        e1 = f1;
        e2 = f2;
    }
    
    return (int)e0;
}