91. Decode Ways

這題我覺得蠻有意思的, 但在思索片刻後還是沒想法

首先是遞迴, 如果 p 已經是跟字串長度一樣大了, 我們就回傳1, 然後逐從疊加回去,

如果s[p] == ‘0’, 回傳0, 因為他不會有結果, 他一定要跟別人搭配

另外假設i < n-1且 s[p] == ‘1’, 他可以往後兩個在尋找組合, 因為1搭配任何數字都可以在組成別的字母

s[p] == ‘2’且s[p + 2] < ‘7’符合的話也是

這樣時間複雜度是O(2^n) 太久了 會tle

class Solution {
public:
    int numDecodings(int p, string &s){
        int n = s.size();
        if(p == n){
            return 1;
        }
        if(s[p] == '0'){
            return 0;
        }
        int res = numDecodings(p+1, s);
        if( p < n - 1 && (s[p] == '1' || (s[p] == '2' && s[p + 1] < '7')))
            res += numDecodings(p + 2, s);
        return res;
    }
int numDecodings(string s) {
        return s.empty()? 0 : numDecodings(0, s);
    }
};

接著就要想到DP了,

好難

我們從後面看回來, 假設我們遇到0, 這個dp的值就是0,因為0開頭的不可能存在任何組合

倘若是其他數字當開頭, 一般來說 dp[i] = dp[i + 1], 假設兩個都是3, 那組合數是不會有變化的, 但假設, s[i] == ‘1’, 以及 s[i] == ‘2’ && s[i + 1] < ‘7’, 我們就要直接到dp[i + 2], 去選取另一種組合的所有可能, 我再次甘拜下風

class Solution {
public:
    int numDecodings(string s) {
        int n = s.size();
vector<int> dp(n + 1, 0);
        dp[n] = 1;
        for(int i = n -1;i>=0;i--){
            if(s[i] == '0'){
                dp[i] = 0;
            }else{
                dp[i] = dp[i + 1];
                if(i < n - 1 && (s[i] == '1' || (s[i] == '2' && s[i + 1] < '7'))){
                    dp[i] += dp[i + 2];
                }
            }
        }
        return s.empty()?0:dp[0];
    }
};