Problem: 639. Solution碼方法 II

Solution題過程

自己做出來的困難題，優先考慮這道題91. Decode Ways，動態規劃遞推公式主要考慮當前字符和前一個字符，若單獨考慮當前字符[1-9]，則dp[i] = dp[i-1]，若單獨考慮當前字符*，則dp[i] = dp[i-1] * 9；若合起來考慮當前字符和前一個字符（10<=W<=99），則dp[i] = dp[i-2]

初始化：若字符串空，則dp[0] = 1，若s[0]'*'則dp[1]=9，若s[0]'0’則dp[1]=0，若s[0]==其他則dp[1]=1

遞推公式：當前字符和前一個字符，

若當前字符s[i-1]=='0’且前一個字符s[i-2]>='3’不可decode返回0，

若當前字符s[i-1]'0’且前一個字符s[i-2]'0’不可decode返回0

若s[i-2]‘*’ && (isdigit(s[i-1]) && s[i-1]‘0’)，只有當 * = 1或者 *=2時才可以合併考慮dp[i] = (dp[i-2] * 2) % modulo; 不可以單獨考慮當前字符’0’

若s[i-2]==‘*’ && (isdigit(s[i-1]) && s[i-1]<=‘6’)，dp[i] = (dp[i-1] + dp[i-2] * 2) % modulo; 可單獨考慮當前字符，或者合併考慮兩者（ *只能取【1，2】）

若s[i-2]==‘*’ && (isdigit(s[i-1]) && s[i-1]>=‘7’)， dp[i] = (dp[i-1] + dp[i-2]) % modulo; 可單獨考慮當前字符，或者合併考慮兩者（ *只能取【1】）

若s[i-2]‘*’ && s[i-1]‘*’，dp[i] = (dp[i-1] * 9 + dp[i-2] * 15) % modulo; 可單獨考慮當前字符*共9種可能，或者合併考慮兩者(s[i-2]取1則s[i-1]9種可能，s[i-2]取2則s[i-1]6種可能，9+6=15)

若s[i-2]‘0’ && s[i-1]‘*’，dp[i] = (dp[i-1] * 9) % modulo; 只能單獨考慮當前字符，9種可能，不能合併考慮

若s[i-2]‘1’ && s[i-1]‘*’，dp[i] = (dp[i-1] * 9 + dp[i-2] * 9) % modulo；單獨考慮則9種，合併考慮也是9種

若s[i-2]‘2’ && s[i-1]‘*’，dp[i] = (dp[i-1] * 9 + dp[i-2] * 6) % modulo;，單獨考慮則9種，合併考慮6種

若s[i-2] >= ‘3’ && s[i-1]==‘*’，dp[i] = (dp[i-1] * 9) % modulo;，只能單獨考慮的，不能合併考慮

若s[i - 2] == ‘0’，dp[i] = dp[i - 1] % modulo; 只能單獨考慮

若s[i - 1] == ‘0’ && s[i - 2] <= ‘2’，只能合併考慮，dp[i] = dp[i - 2] % modulo;

若s[i - 2] >= ‘3’，只能單獨考慮，dp[i] = dp[i - 1] % modulo;

若s[i - 2] == ‘2’ && s[i - 1] > ‘6’，只能單獨考慮，dp[i] = dp[i - 1] % modulo;

若s[i - 2] <= ‘2’ && s[i - 1] <= ‘6’，既可以單獨考慮，也可以合併考慮， dp[i] = (dp[i - 1] + dp[i - 2]) % modulo;

若s[i - 2] == ‘1’， dp[i] = (dp[i - 1] + dp[i - 2]) % modulo; 既可以單獨考慮，也可以合併考慮， dp[i] = (dp[i - 1] + dp[i - 2]) % modulo;

Code

class Solution {
public:
    int numDecodings(string s) {
        const int modulo = 1e9 + 7;
        vector<long long> dp(s.length() + 1);
        if (s[0] == '0') return 0;
        dp[0] = 1;
        if(s[0]=='0') {
            dp[1] = 0;
        } else if(s[0]=='*') {
            dp[1] = 9;
        } else {
            dp[1] = 1;
        }
        for (int i = 2; i <= s.length(); i++) {
            if (s[i - 1] == '0' && s[i - 2] >= '3') {
                return 0;
            }
            else if (s[i - 1] == '0' && s[i - 2] == '0') {
                return 0;
            }
            else if(s[i-2]=='*' && (isdigit(s[i-1]) && s[i-1]=='0')) {
                dp[i] = (dp[i-2] * 2) % modulo;
            }
            else if(s[i-2]=='*' && (isdigit(s[i-1]) && s[i-1]<='6')) {
                dp[i] = (dp[i-1] + dp[i-2] * 2) % modulo;
            }
            else if(s[i-2]=='*' && (isdigit(s[i-1]) && s[i-1]>='7')) {
                dp[i] = (dp[i-1] + dp[i-2]) % modulo;
            }
            else if(s[i-2]=='*' && s[i-1]=='*') {
                dp[i] = (dp[i-1] * 9 + dp[i-2] * 15) % modulo;
            }
            else if(s[i-2]=='0' && s[i-1]=='*') {
                dp[i] = (dp[i-1] * 9) % modulo;
            }
            else if(s[i-2]=='1' && s[i-1]=='*') {
                dp[i] = (dp[i-1] * 9 + dp[i-2] * 9) % modulo;
            } 
            else if(s[i-2]=='2' && s[i-1]=='*') {
                dp[i] = (dp[i-1] * 9 + dp[i-2] * 6) % modulo;
            } 
            else if(s[i-2] >= '3' && s[i-1]=='*') {
                dp[i] = (dp[i-1] * 9) % modulo;
            }
            else if (s[i - 2] == '0') {
                dp[i] = dp[i - 1] % modulo;
            }
            else if (s[i - 1] == '0' && s[i - 2] <= '2') {
                dp[i] = dp[i - 2] % modulo;
            }
            else if (s[i - 2] >= '3') {
                dp[i] = dp[i - 1] % modulo;
            }
            else if (s[i - 2] == '2' && s[i - 1] > '6') {
                dp[i] = dp[i - 1] % modulo;
            }
            else if (s[i - 2] <= '2' && s[i - 1] <= '6') {
                dp[i] = (dp[i - 1] + dp[i - 2]) % modulo;
            }
            else if (s[i - 2] == '1') {
                dp[i] = (dp[i - 1] + dp[i - 2]) % modulo;
            }
        }
        return dp[s.length()];
    }
};