91 Decode Ways

這一題的核心觀念是要從字串的最後面往前計算dp的陣列。dp[n] = 1假設無論如何一定有一種表示法(每一個digit自己是一位，都沒有跟其他digit合併)。

另外要注意的是，如果碰到0，就把當下那一格的dp[i]存成0。

    int dp[] to save # of ways to decode current element
    為了簡化規則:
    dp[n] = 1
    dp[n-1] = s.charAt(n-1) == 0 ? 0 : 1
    從s的倒數第二個digit往前讀
        如果digit==0, continue; -> dp[i]為0，0開頭的string不valid
        如果digit和後一個digit組起來<=26
            dp[i] = dp[i+1]+dp[i+2]
        不然 dp[i] = dp[i+1] -> 只能add到已存在的組合中

    return dp[0]

public class Solution {
    public int numDecodings(String s) {
        /*
        265 -> 2,6,5; 26,5;
        214 -> 2,1,4; 21,4; 2,14;
        2121 -> 2,1,2,1;

        2 -> 2
        6 -> 2,6; 26;
        5 -> 2,6,5; 26,5;

        2 -> 2
        1 -> 2,1; 21;
        4 -> 2,1,4; 2,14; 21,4

        2 -> 2
        1 -> 2,1; 21;
        2 -> 2,1,2; 2,12; 21,2
        1 -> 2,1,2,1; 2,1,21; 2,12,1; 21,2,1; 21,21;

        2 -> 2
        1 -> 2,1; 21;
        2 -> 2,1,2; 2,12; 21,2
        7 -> 2,1,2,7; 2,12,7; 21,2,7

        2 -> 2
        1 -> 2,1; 21;
        2 -> 2,1,2; 2,12; 21,2
        0 -> 2,1,20; 21,20; 2,10;

        3 -> 3,12,7; 3,1,2,7;
        1 -> 12,7; 1,2,7;
        2 -> 2,7
        7 -> 7

        3 -> 3
        1 -> 3,1;
        3 -> 3,1,3; 3,13;
        0 -> 

        2 -> 20,1,3; 20,13;
        0 -> 
        1 -> 1,3; 13;
        3 -> 3;

        3 -> 3,1,20
        1 -> 1,20
        2 -> 20
        0 -> 

        0的規則：
        如果0和前一個digit不能組成26以內的數字，直接return 0
        0的後一個digit會和0那格dp數字一樣
        sol1:
        List<List<Integer>> list;
        list.add(s.charAt(0) - '0')
        每讀一個char in s,
            依序讀list中的entry
                把char直接add到現在的entry，將這個List<Integer>加入一個暫存的List<List<Integer>>
                檢查是否可以把char append到現在的entry的最後一個integer，若可以，將這個List<Integer>加入一個暫存的List<List<Integer>>
            list = 暫存的List<List<Integer>>
        return list.size();
        */
        int n=s.length();
        if(s=="" || n==0)
            return 0;
        if(s.charAt(0)=='0')
            return 0;

        int dp[] = new int[n+1];
        dp[n]=1;
        dp[n-1] = s.charAt(n-1) == '0' ? 0 : 1;
        for(int i = n-2; i>=0; i--){
            int digit = s.charAt(i)-'0';
            if(digit==0)    continue;
            if(digit*10 + (s.charAt(i+1)-'0') <=26){
                dp[i] = dp[i+1]+dp[i+2];
            }
            else{
                dp[i] = dp[i+1];
            }
        }
        return dp[0];

    }
}