LeetCode91. 解码方法

---

包含 A-Z 的字母的消息通过以下规则编码：

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

给定一个包含数字的编码消息，请确定解码方法的总数。

例如，
给定消息为 "12"， 它可以解码为 "AB"（1 2）或 "L"（12）。

"12" 的解码方法为 2 种。

思路：

可以看作一个动态规划的问题，

首先，如果第一位上是0，那么无法转码，返回0；

其次，每次转码，都可以看看第i位跟第i-1位的数字是否小于等于26，如果符合的话，我们在i-2位上解码；如果第i位不等于0的话，说明我们相当于在第i-1位上解码。如果两个都符合，相当于：dp[i] = dp[i-1] + dp[i-2];

代码：

注意两位数时候的情况，错了很麻烦。 

    public static int numDecodings(String s) {
        if(s.length()==0){
            return 0;
        }
        int[] dp = new int[s.length()];
        dp[0] = s.charAt(0)=='0'?0:1;
        if(s.length()==1){
            return dp[0];
        }
        int k = s.charAt(0) > '0' && s.charAt(1) > '0'? 1:0;
        dp[1] = k + (s.charAt(0) == '1' || s.charAt(0) == '2' && s.charAt(1) <= '6' ? 1:0);
        for (int i = 2; i < dp.length; i++) {
            if(s.charAt(i)!='0'){
                dp[i] += dp[i-1];
            }
            if(s.charAt(i-1)=='1'||s.charAt(i-1)=='2'&&s.charAt(i)<='6'){
                dp[i] += dp[i-2];
            }
        }
        return dp[s.length()-1];
    }