Java实现 LeetCode 639解码方法 2（递推）

淡淡的烟草味﹌ 2023-07-20 12:23 53阅读 0赞

## 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()];
    }
    }