Decode Ways

A message containing letters from A-Z is being encoded to numbers using the following mapping:

'A' -> 1
'B' -> 2
...
'Z' -> 26
Given an encoded message containing digits, determine the total number of ways to decode it.

For example,
Given encoded message "12", it could be decoded as "AB" (1 2) or "L" (12).

The number of ways decoding "12" is 2.

属于一维动态规划的题目，首先我们构造一个dp数组，题目中要求只有数字1 - 26才是合法数字，当出现‘0’的时候就无法解码。因此我们可以首先判断一下字符串的第一个字符是否为‘0’，如果为‘0’我们可以直接返回0，当然如果字符串本身为空，也是直接返回0。如果不为0，这时我们让dp[0] = 1,对应了第一个字符只有一种解码方式, 对于到第i个字符时，如果它不为‘0’，它可能的情况至少有dp[i - 1]种，然后我们查看第i个字符和第i- 1 个字符构成的数字是否在1-26之间，如果在，那么到第i个字符总共有dp[i - 1] + dp[i - 2]种，这时（i > 1, i == 1 的时候 有dp[i - 1] + 1 种) ，这样递推式就有了，代码如下：

public class Solution {
    public int numDecodings(String s) {
        if(s == null || s.length() == 0 || s.charAt(0) == '0') 
            return 0;
        int[] dp = new int[s.length()];
        dp[0] = 1;
        for(int i = 1; i < s.length(); i++) {
            if(s.charAt(i) != '0')
                dp[i] = dp[i - 1];
            if(s.charAt(i - 1) != '0') {
                int code = Integer.parseInt(s.substring(i - 1, i + 1));
                if(code >= 1 && code <= 26) {
                    if(i > 1) {
                        dp[i] += dp[i - 2];
                    } else {
                        dp[i] += 1;
                    }
                }
            }
        }
        return dp[s.length() - 1];
    }
}