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.

Solution1: DP, constant space
We can solve this problem recursively. But it will time out. Because we calculate the same substring several times, which is not necessary. We can use DP to make it faster.
有两种方式：第一种新加进来的数字自己表示一个字符，那么解析的方式有res[i-1]种，第二种就是新加进来的数字和前一个数字凑成一个字符，解析的方式有res[i-2]种。
（1）00：res[i]=0（无法解析，没有可行解析方式)
（2）10, 20：res[i]=res[i-2]（第二种情况成立）
（3）11-19, 21-26：res[i]=res[i-1]+res[i-2]（两种情况都可行）
（4）27-99：res[i]=res[i-1]（第一种情况成立）
只要进行一遍扫描，然后依次得到维护量，算法的时间复杂度是O(n)。空间上每次只需要前两位的历史信息，所以只需要维护三个变量然后迭代赋值就可以了，所以空间复杂度是O(1)。

public class Solution {
    // （1）00：res[i]=0（无法解析，没有可行解析方式）；
    // （2）10, 20：res[i]=res[i-2]（只有第二种情况成立）；
    // （3）11-19, 21-26：res[i]=res[i-1]+res[i-2]（两种情况都可行）；
    // （4）27-99：res[i]=res[i-1]（只有第一种情况可行）；
    public int numDecodings(String s) {
        if(s == null || s.length() == 0 || s.charAt(0) == '0') {
            return 0;
        }
        
        int num1 = 1;
        int num2 = 1;
        int num3 = 1;
        for(int i = 1; i < s.length(); i++) {
            if(s.charAt(i) == '0') {
                if(s.charAt(i - 1) == '1' || s.charAt(i - 1) == '2') {  //10, 20：res[i]=res[i - 2]
                    num3 = num1;
                }else {
                    return 0;
                }
            }else {
                if(s.charAt(i - 1) == '0' || s.charAt(i - 1) >= '3') {  //res[i] = res[i - 1]
                    num3 = num2;
                }else {
                    if(s.charAt(i - 1) == '2' && s.charAt(i) >= '7' && s.charAt(i) <= '9') {  //27-99, res[i] = res[i - 1]
                        num3 = num2;
                    }else {
                        num3 = num2 + num1;  //11-19, 21-26：res[i]=res[i-1]+res[i-2]
                    }
                }
            }
            num1 = num2;
            num2 = num3;
        }
        return num3;
    }
}

Solution2: DP

从头到尾扫这个String，比如我们想知道到，从第一位到dp[i]这一位组成的String，有多少种解码组合，那么有两种情况

第一：如果dp[i]所对应的的单个字符可以解码，那么dp[i]就包括前dp[i-1]位所积累的组合数 dp[i] = dp[i-1] 

第二：如果不仅dp[i]所对应的的单个字符可以解码，dp[i-1] － dp[i]，两个字符组成的也可以解码，那么不仅包括dp[i-1]积累的组合数，也包括dp[i-2]位积累的组合数 dp[i] = dp[i-1] + dp[i-2]

设置动态数组dp[n+1]。dp[i]表示从1~i的decode ways的个数。

时间复杂度是O(n).

public class Solution {
    public int numDecodings(String s) {
        if(s == null || s.length() == 0)
            return 0;
        
        if(s == "0")
            return 0;
        
        int[] n = new int[s.length() + 1];
        n[0] = 1;
        
        if(isValid(s.substring(0, 1)))
            n[1] = 1;
        else
            n[1] = 0;
        
        for(int i = 2; i <= s.length(); i++) {
            if(isValid(s.substring(i - 1, i)))
                n[i] += n[i - 1];
            if(isValid(s.substring(i - 2, i)))
                n[i] += n[i - 2];
        }
        return n[s.length()];

    }
    
    public boolean isValid(String s) {
        if(s.charAt(0) == '0')
            return false;
        int num = Integer.parseInt(s);
        if(num > 0 && num <= 26)
            return true;
        return false;
    }
}