91. 解码方法

柔光的暖阳◎ 2022-10-09 00:40 177阅读 0赞

> 一条包含字母 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" 在映射中并不等价。
> 
> 给你一个只含数字的 非空 字符串 s ，请计算并返回 解码 方法的 总数 。
> 
> 示例 1：
> 
> 输入：s = "12"  
> 输出：2  
> 解释：它可以解码为 "AB"（1 2）或者 "L"（12）。  
> 示例 2：
> 
> 输入：s = "226"  
> 输出：3  
> 解释：它可以解码为 "BZ" (2 26), "VF" (22 6), 或者 "BBF" (2 2 6) 。  
> 示例 3：
> 
> 输入：s = "0"  
> 输出：0
> 
>

class Solution {
        public int numDecodings(String s) {
            int []dp=new int[s.length()];//保存当前位 的结果
            dp[0]=1;//第1位只有一种结果 
            if(s.charAt(0)=='0'){
                return 0;
            }
    
            //dp[i-1]->当前字符的映射方法    dp[i-2] 上一个字符的映射方法
            for(int i=1;i<s.length();i++){
                if(s.charAt(i)=='0'){
                    //出现0,但0 前不是1 2
    
                    if(s.charAt(i-1)!='1'&&s.charAt(i-1)!='2'){
                        return 0;
                    }
    
                    dp[i]=(i==1?dp[0]:dp[i-2]); //防止越界  要进行判断i是否=1           
                }
                else  if(s.charAt(i-1)=='1'||(s.charAt(i-1)=='2'&&s.charAt(i)<='6')){
                    //出现 1XX或者 20->26    可以差分为两种结果 合并
                                  
                        dp[i]=(i==1? dp[0]+1:dp[i-1]+dp[i-2]);    //防止越界  要进行判断i是否=1           
         
                }else{
                    dp[i]=dp[i-1];//当前字符无效
                }
            }
    
            return dp[s.length()-1];
    
        }
    }