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]數(shù)組保存有多少種方法可以decode長(zhǎng)度到0..i的string
12121[2] 每到一個(gè)第i個(gè)長(zhǎng)度時(shí)的新字符c時(shí)垮抗，有兩種情況席函，所以dp[i] = 方法數(shù)量(情況1) + 方法數(shù)量(情況2)： 第一種情況就是c獨(dú)立被decoded，方法數(shù)量(情況1) = dp[i - 1]唐含，前提是：c不是零；第二種情況就是 c和上一位c'一起作為兩位數(shù)c'c 被decoded彻亲，這樣 方法數(shù)量(情況2) = dp[i - 2]堕担，前提是c'c是屬于[10, 26]即能夠被decoded的。
所以在實(shí)現(xiàn)時(shí)座掘，當(dāng)滿足情況1時(shí)递惋，dp[i] += dp[i - 1]; 當(dāng)滿足情況2時(shí)，dp[i] 繼續(xù)+= dp[i - 2];

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

Solution2：優(yōu)化Space DP

思路： 根據(jù)Solution1溢陪，可知dp[i] only relies on dp[i - 1] and dp[i - 2]萍虽，所以之間的可以不用keep，過去dp只用兩個(gè)變量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;
    }
}