Decode Ways LeetCode solution in C++

1
class Solution {
2
 public:
3
  int numDecodings(string s) {
4
    if (s[0] == 0) return 0;
5
    int n = s.length();
6
    vector<int> dp(n + 1, 0);
7

8
    // Storing DP[n-1]
9
    if (s[n - 1] == '0')
10
      dp[n - 1] = 0;
11
    else
12
      dp[n - 1] = 1;
13

14
    if (n == 1) return dp[0];
15

16
    // Storing DP[n-2]
17
    if (s[n - 2] == '0')
18
      dp[n - 2] = 0;
19
    else {
20
      string temp;
21
      temp.push_back(s[n - 2]);
22
      temp.push_back(s[n - 1]);
23

24
      int x = stoi(temp);
25
      if (x < 27) dp[n - 2] = 1;
26
      dp[n - 2] += dp[n - 1];
27
    }
28

29
    for (int i = n - 3; i >= 0; i--) {
30
      if (s[i] == '0') continue;
31

32
      string temp;
33
      temp.push_back(s[i]);
34
      temp.push_back(s[i + 1]);
35

36
      int x = stoi(temp);
37
      if (x < 27) dp[i] = dp[i + 2];
38
      dp[i] += dp[i + 1];
39
    }
40

41
    return dp[0];
42
  }
43
};