题目

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

'A' -> 1
'B' -> 2
...
'Z' -> 26
给定一个包含数字的编码消息，请确定解码方法的总数。

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

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

代码

    public  int numDecodings(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        int[] dp = new int[s.length() + 1];//dp[i]表示长度为i能编码的种数
        dp[0] = 1;
        dp[1] = s.charAt(0) == '0' ? 0 : 1;
        for (int i = 2; i < dp.length; i++) {
            int first = Integer.parseInt(s.substring(i - 1, i));
            int second = Integer.parseInt(s.substring(i - 2, i));
            if (first > 0 && first <= 9) {
                //看成一个单数
                dp[i] += dp[i - 1];
            }
            if (second >= 10 && second <= 26) {
                //看成一个小于26两位数
                dp[i] += dp[i - 2];
            }
        }
        
        return dp[s.length()];
    }