[Leetcode] 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 problem, use dp[i] to indicate the number of ways to decode the string ended at i:

1. if s[i] == 0, only when i > 0 and s[i-1] = 1 or s[i-1] = 2 do we have the way to decode, so in this case, dp[i] = dp[i-2] if i > 1 or dp[i] = 1; otherwise, we could not decode the string
2. when s[i] != 0, we at least have one way to decode, thus, dp[i] = dp[i-1] if i > 0 or dp[i] = 1 if i = 0. Then we try to see if we could use this digit with its prior one to decode one character, that is, the s[i-1... i] is a number between 10 and 26 inclusively, in this case we add the prior's way, which is dp[i-2].

    public int numDecodings(String s) {
        int n = s.length();
        if(n == 0)
            return 0;
        int[] dp = new int[n];
        for(int i = 0; i < n; i++) {
            if(s.charAt(i) == '0') {
                if(i > 0 && (s.charAt(i-1) == '1' || s.charAt(i-1) == '2'))
                    dp[i] = (i > 1 ? dp[i-2] : 1);
                else
                    return 0;
            }
            else {
                dp[i] = (i > 0 ? dp[i-1] : 1);
                if(i > 0) {
                    int num = Integer.parseInt(s.substring(i-1, i+1));
                    if(num >= 10 && num <= 26) 
                        dp[i] += (i > 1 ? dp[i-2] : 1);
                }
            }
        }
        return dp[n-1];
    }