欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

Java实现 LeetCode 639解码方法 2(递推)

程序员文章站 2022-03-05 10:00:14
...

639. 解码方法 2

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

'A' -> 1
'B' -> 2
...
'Z' -> 26

除了上述的条件以外,现在加密字符串可以包含字符 '‘了,字符’'可以被当做1到9当中的任意一个数字。

给定一条包含数字和字符’*'的加密信息,请确定解码方法的总数。

同时,由于结果值可能会相当的大,所以你应当对109 + 7取模。(翻译者标注:此处取模主要是为了防止溢出)

示例 1 :

输入: “*”
输出: 9
解释: 加密的信息可以被解密为: “A”, “B”, “C”, “D”, “E”, “F”, “G”, “H”, “I”.
示例 2 :

输入: “1*”
输出: 9 + 9 = 18(翻译者标注:这里1可以分解为1, 或者当做1*来处理,所以结果是9+9=18)
说明 :

输入的字符串长度范围是 [1, 105]。
输入的字符串只会包含字符 ‘*’ 和 数字’0’ - ‘9’。

PS:
复杂的递推

class Solution { 

      public static int numDecodings(String s) {
      if(s == null || s.length() == 0)
        return 0;
    if(s.length() == 1)
        return s.charAt(0) == '0' ? 0 : s.charAt(0) == '*' ? 9 : 1;
    if(s.charAt(0) == '0')
        return 0;

    char[] chars = s.toCharArray();
    long[] dp = new long[s.length() + 1];
    dp[0] = 1;
    dp[1] = chars[0] == '*' ? 9 : 1;
    for(int i = 2; i <= chars.length ; i ++){
        char first = chars[i - 2]; //表示第i - 1个字符
        char second = chars[i - 1]; //表示第i个字符

        //对于dp[i - 1]
        if(second == '*')
            dp[i] += 9 * dp[i - 1];
        else if(second > '0')
            dp[i] += dp[i - 1];

        //对于dp[i - 2]
        if(first == '*'){
            if(second == '*') {
              //26-10-1   *不能代替0
                dp[i] += 15 * dp[i - 2];
            }else if(second <= '6')
                    //11-26只有1    2两种选择
                dp[i] += 2 * dp[i - 2];
            else//都不是的话只能是1
                dp[i] += dp[i - 2];
        }else if(first == '1' || first == '2'){
            if(second == '*'){
                //11-19  或者21-26
                dp[i] += first == '1' ? 9 * dp[i - 2] : 6 * dp[i - 2];
            }else if((first - '0') * 10 + second - '0' <= 26){
                //或者直接是死的
                dp[i] += dp[i - 2];
            }
        }
        dp[i] %= 1000000007;
    }
    return (int)dp[s.length()];
}
}