Decode Ways leetcode

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.
时间复杂度O(n), 空间O(n) 用%3的办法可以把空间复杂度降低为O(1)

state: dp[i]表示前i个字符的总共decode的可能性

function：1. 如果第i个字符(substring[i-1,i] )可以被decode， dp[i] = dp[i-1]

                2. 如果i-1, i字符（substring[i-2,i-1]）可以decode， dp[i] += dp[i-1]

inital: dp[0] = 1    因为当长度为2时候找第二种情况就等于dp[0]， 此时应该为1而不是0

         dp[1] = 0 或者1 之所以要定义dp[1]因为我们要判定i-2的情况 所以单独列出来

return dp[s.length()]

注意数组里的index ==String里的index+1 

public class Solution {
    public int numDecodings(String s) {
        int n = s.length();
        if (n == 0) {
            return 0;
        }
        int[] dp = new int[n + 1];
        dp[0] = 1;
        if (isValid(s.substring(0,1))) {
            dp[1] = 1;
        } else {
            dp[1] = 0;
        }
        for (int i = 2; i <= n; i++) {
            if (isValid(s.substring(i-1, i))) {//最后一位是否符合条件
                dp[i] = dp[i-1];
            } 
            if (isValid(s.substring(i-2, i))) {//最后两位是否符合条件
                dp[i] += dp[i-2];
            }
            
        }
        return dp[n];
    }
    private boolean isValid(String s) {
        if (s.charAt(0) == '0') {
            return false;
        }
        int tem = Integer.parseInt(s);//把string变为int
        return tem >= 1 && tem <= 26;
    }
}