Leetcode 91：解码方法 Java实现

题目描述：
一条包含字母 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) 。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/decode-ways
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解：动态规划
这道题的动态规划方程不难得出，假设 dp[i-1] 是表示到 i-1 的字符串的解码方法有多少种，那么在最后面加多一个字符进去，也就是 dp[i] 的时候：
 ①假设最后一个字符单独解码，那么 dp[i] = dp[i-1]
 ②假设最后一个字符与前一个字符一起解码，那么 dp[i] = dp[i-2]，但是与前一个字符一起解码的时候必须是大于等于10小于等于26的。

然而这道题难的地方在于字符串中出现了 ‘0’ 要怎么处理？

首先如果‘0’出现在字符串起始位置，那么这个字符串是无法解码的，即解码方法为 0；
其次出现在其他位置，那么就不能单独解码，只能与前一个字符一起解码，与前一个字符一起解码时，必须要大于等于10小于等于26。

所以动态规划方程是：
边界情况：
 ① 当 s[0] = ‘0’ ，字符串无法解码，返回0；当 s[0] != ‘0’，dp[0] = 1
 ② 当 s[1] != ‘0’，dp[1]=dp[0] ；当 Int(s[0],s[1]) >= 10 && Int(s[0],s[1]) <= 26, dp[1]=dp[0]+1；
注：Int(s[i-1],s[i]) 表示将 s[i-1]和s[i]两个字符转为相对应的数字，比如：Int(1,2) = 12;

非边界情况：当 s[i] != ‘0’ 时，dp[i] = dp[i-1]；在前一个条件执行后，当 Int(s[i-1],s[i]) >= 10 && Int(s[i-1],s[i]) <= 26，dp[i] += dp[i-2];

（可能说的有点乱。。结合代码看的话应该就可以看懂）

public int numDecodings(String s) {
        
        //其实位置为0则无法解码
        if (s.charAt(0) == '0') {
            return 0;
        }

        //长度为1并且这个字符不为0的情况下，解码方法就只有1种
        if (s.length() == 1) {
            return 1;
        }

        int n = s.length();
        char[] chars = s.toCharArray();
        int[] dp = new int[n];
        
        // 边界情况，dp[0]=1 (s[0] != '0')
        dp[0] = 1;

        // 边界情况，dp[1] = dp[0] 还是 dp[1] = dp[0] + 1
        int num = 10 * (chars[0]-'0') + (chars[1]-'0');
        if (chars[1] != '0') {
            dp[1] = dp[0];
        }
        if (num >= 10 && num <= 26) {
            dp[1]++;
        }

        // dp[i] = dp[i-1] 或 dp[i] = dp[i-1] + dp[i-2]
        for (int i = 2; i < n; i++) {
            if (chars[i] != '0') {
                dp[i] = dp[i-1];
            }

            num = 10 * (chars[i-1]-'0') + (chars[i]-'0');
            if (num >= 10 && num <= 26) {
                dp[i] += dp[i-2];
            }
        }

        return dp[n-1];
    }

虽然这次题解写的不太好，但是还是求给一颗GitHub的start~
https://github.com/zzdreamz/Leetcode-practice