leetcode算法练习【91】解码方法

朱雀 2023-02-14 10:22 126阅读 0赞

### 文章目录 ###

*   *   *   *  所有题目源代码：\[Git地址\](https://github.com/ch98road/leetcode)
             *  题目
             *  方案：动态规划
             *   *  复杂度计算

#### 所有题目源代码：[Git地址][Git] ####

#### 题目 ####

一条包含字母 A-Z 的消息通过以下方式进行了编码：
    
    'A' -> 1
    'B' -> 2
    ...
    'Z' -> 26
    给定一个只包含数字的非空字符串，请计算解码方法的总数。
    
    示例 1:
    
    输入: "12"
    输出: 2
    解释: 它可以解码为 "AB"（1 2）或者 "L"（12）。
    示例 2:
    
    输入: "226"
    输出: 3
    解释: 它可以解码为 "BZ" (2 26), "VF" (22 6), 或者 "BBF" (2 2 6) 。

#### 方案：动态规划 ####

*  这道题比较烦的就是排除特殊情况比如30 、00 、27这种的，思路本身还是很简单的

class Solution { 
            public int numDecodings(String s) { 
                
                //每次都是 1 、2步
                //自然想到动态规划
                char[] str = s.toCharArray();
                int[] res = new int[str.length];
                res[0] = 1;
                if(str[0]=='0') return 0;
                if(str.length==1) return 1;
                if(10*(str[0]-'0')+str[1]-'0'<=26&&10*(str[0]-'0')+str[1]-'0'>10&&(str[1]-'0')>0){ 
                    res[1] = 2;
                }
                else{ 
                    if(str[1]=='0'&&str[0]>='3') return 0;
                    res[1] = 1;
                }
                for(int i = 2;i<res.length;i++){ 
                    if(str[i]=='0'&&(str[i-1]=='0'||str[i-1]>='3')) return 0;
                    if(10*(str[i-1]-'0')+str[i]-'0'>10&&10*(str[i-1]-'0')+str[i]-'0'<=26&&(str[i]-'0')>0&&(str[i-1]-'0')>0){ 
                        res[i] = res[i-1]+res[i-2];
                    }else{ 
                        if(str[i]=='0'){ 
                            res[i] = res[i-2];
                        }else{ 
                            res[i] = res[i-1];
                        }
                    }
                }
                return res[str.length-1];
            }
        }

##### 复杂度计算 #####

*  时间复杂度：O(n)
 *  空间复杂度：O(n)

[Git]: https://github.com/ch98road/leetcode