[LeetCode每日一题]91. 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 a non-empty string containing only digits, determine the total number of ways to decode it.

Example:
Input: "226"
Output: 3
Explanation: It could be decoded as "BZ" (2 26), "VF" (22 6), or "BBF" (2 2 6).

A-Z分别编码成1-26，给定一串编码后的数字串，问我们有多少种合法的解码方法。 这道题可以用动态规划的方法解决，解题思路和LeetCode-70爬楼梯问题类似定义状态空间dp[i]表示从第1个到第i个数字的解码方法，求解状态空间时有以下两种情况： 1.第i个字符单独解码，则dp[i] == dp[i-1]; 2.第i个字符和第i-1个字符一同解码，则dp[i] == dp[i-2]。 综合考虑以上两种情况以及边界条件，代码如下：

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