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.

Solution:
1-d dynamic programming question.
O(n) space can be reduced to constant space:
iteration formula: dp[i] = valid(dp[i-1]) + valid(dp[i-2]).
It means that letter i could itself decoded as a letter, or combine its previous to decode as a letter.

//////////////////// usually, "the number of ways" is always related to DP. /////////////////////////
public class Solution {
    public int numDecodings(String s) {
        // corner case
        int n = s.length();
        if(n == 0) 
            return 0;
        
        int[] ways = new int[n];
        for(int i = 0; i < n; i++){
            if(i == 0){
                // zero is invalid to be a letter
                ways[i] = s.charAt(i) == '0' ? 0 : 1;
            }
            else{
                // it can be decoded in one letter or in two letters (with its previous one)
                ways[i] = s.charAt(i) == '0' ? 0: ways[i-1];
            
                String str = s.substring(i-1,i+1);
                int val = Integer.valueOf(str);
                if(val >= 10 && val <= 26){
                    if(i == 1)
                        ways[i] += 1;
                    else
                        ways[i] += ways[i-2];
                }
            }
        }
        return ways[n-1];
    }
}