Decode Ways II LeetCode solution in C++

1
#define ll long long
2
class Solution {
3
 public:
4
  ll numDecodings(string s) {
5
    ll M = 1000000007;
6
    ll dp[s.size() + 1];
7
    memset(dp, 0, sizeof(dp));
8

9
    dp[0] = 1;
10

11
    for (int i = 1; i <= s.size(); i++) {
12
      if (s[i - 1] == '*' and i == 1)
13
        dp[i] = 9;
14
      else if (s[i - 1] == '0' and i == 1)
15
        dp[i] = 0;
16
      else if (i == 1)
17
        dp[i] = 1;
18
      else {
19
        // now we need to check previous 2 characters for *,digit combination
20
        if (s[i - 1] == '*')
21
          dp[i] += (9 * dp[i - 1]) % M;
22
        else {
23
          if (s[i - 1] == '0') // since previous zero combination not possible
24
                               // according to question no partition can take
25
                               // place with a previous character 0
26
            dp[i] = 0;
27
          else
28
            dp[i] += dp[i - 1] % M;
29
        }
30

31
        // for(int i = 0; i <= s.size(); i++)
32
        // cout << dp[i] << " ";
33
        // cout << "\n";
34

35
        if (s[i - 2] == '*') {
36
          if (s[i - 1] == '*')
37
            dp[i] += (15 * dp[i - 2]) % M;
38
          else if (s[i - 1] > '6') // only 1 way
39
            dp[i] += dp[i - 2] % M;
40
          else
41
            dp[i] += (2 * dp[i - 2]) % M;
42

43
        } else if (s[i - 2] == '1') {
44
          if (s[i - 1] == '*') {
45
            dp[i] += (9 * dp[i - 2]) % M;
46
          } else
47
            dp[i] += dp[i - 2] % M;
48

49
        } else if (s[i - 2] == '2') {
50
          if (s[i - 1] == '*')
51
            dp[i] += (6 * dp[i - 2]) % M;
52
          else if (s[i - 1] <= '6')
53
            dp[i] += dp[i - 2] % M;
54
        }
55
      }
56
    }
57

58
    // for(int i = 0; i <= s.size(); i++)
59
    // cout << dp[i] << " ";
60
    // cout << "\n";
61

62
    return dp[s.size()] % M;
63
  }
64
};