# LeetCode - 0639. Decode Ways II
### 題目網址：https://leetcode.com/problems/decode-ways-ii/
###### tags: `LeetCode` `Hard` `動態規劃（Dynamic Programming）`

/*
    -LeetCode format-
    Problem: 639. Decode Ways II
    Difficulty: Hard
    
    by Inversionpeter
*/



static const auto Initialize = []{
    ios::sync_with_stdio(false); cin.tie(nullptr);
    return nullptr;
}();

#define MOD 1000000007
int DP[100001] = { 1 };

class Solution {
public:
    int numDecodings(string s) {
        DP[1] = (s[0] == '*' ? 9 : (s[0] != '0' ? 1 : 0));
        for (int i = 1; i != s.size(); ++i)
            if (s[i] == '*') {
                DP[i + 1] = ((long long)DP[i] * 9) % MOD;
                switch (s[i - 1]) {
                    case '*':
                        DP[i + 1] = (DP[i + 1] + (long long)DP[i - 1] * 15) % MOD;
                        break;
                    case '1':
                        DP[i + 1] = (DP[i + 1] + (long long)DP[i - 1] * 9) % MOD;
                        break;
                    case '2':
                        DP[i + 1] = (DP[i + 1] + (long long)DP[i - 1] * 6) % MOD;
                        break;
                }
            }
            else {
                DP[i + 1] = (s[i] != '0' ? DP[i] : 0);
                switch (s[i - 1]) {
                    case '*':
                        if (s[i] <= '6')
                            DP[i + 1] = (DP[i + 1] + (long long)DP[i - 1] * 2) % MOD;
                        else
                            DP[i + 1] = (DP[i + 1] + DP[i - 1]) % MOD;
                        break;
                    case '1':
                        DP[i + 1] = (DP[i + 1] + DP[i - 1]) % MOD;
                        break;
                    case '2':
                        if (s[i] <= '6')
                            DP[i + 1] = (DP[i + 1] + DP[i - 1]) % MOD;
                        break;
                }
            }
        return DP[s.size()];
    }
};