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 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

思路：
dp[i]数组保存有多少种方法可以decode长度到0..i的string
12121[2] 每到一个第i个长度时的新字符c时，有两种情况，所以dp[i] = 方法数量(情况1) + 方法数量(情况2)： 第一种情况就是c独立被decoded，方法数量(情况1) = dp[i - 1]，前提是：c不是零；第二种情况就是 c和上一位c'一起作为两位数c'c 被decoded，这样 方法数量(情况2) = dp[i - 2]，前提是c'c是属于[10, 26]即能够被decoded的。
所以在实现时，当满足情况1时，dp[i] += dp[i - 1]; 当满足情况2时，dp[i] 继续+= dp[i - 2];

Time Complexity: O(N) Space Complexity: O(N)

Solution2：优化Space DP

思路： 根据Solution1，可知dp[i] only relies on dp[i - 1] and dp[i - 2]，所以之间的可以不用keep，过去dp只用两个变量llast_ways, last_ways即可。
Time Complexity: O(N) Space Complexity: O(1)

Solution1 Code：

public class Solution {
    public int numDecodings(String s) {
        int n = s.length();
        if(n == 0) return 0;
        //dp[i]:  the number of ways to decode a string of size i
        int[] dp = new int[n + 1];
        dp[0] = 1;
        dp[1] = s.charAt(0) == '0' ? 0 : 1;

        for(int i = 2; i <= n; i++) {
            int last_one = Integer.valueOf(s.substring(i - 1, i));
            int last_two = Integer.valueOf(s.substring(i - 2, i));
            if(last_one != 0) {
                dp[i] += dp[i - 1];
            }
            if(last_two >= 10 && last_two <= 26) {
                dp[i] += dp[i - 2];
            }
        }
        return dp[n];
    }
}

Solution2 Code：

public class Solution2 {
    public int numDecodings(String s) {
        int n = s.length();
        if(n == 0) return 0;
        
        int llast_ways = 1;
        int last_ways = s.charAt(0) == '0' ? 0 : 1;
        int now_ways = last_ways;

        for(int i = 2; i <= n; i++) {
            now_ways = 0;
            int last_one = Integer.valueOf(s.substring(i - 1, i));
            int last_two = Integer.valueOf(s.substring(i - 2, i));
            if(last_one != 0) {
                now_ways += last_ways;
            }
            if(last_two >= 10 && last_two <= 26) {
                now_ways += llast_ways;
            }
            llast_ways = last_ways;
            last_ways = now_ways;
        }
        return now_ways;
    }
}