```
class Solution {
public:
int numDecodings(string s) {
int n = s.size();
if (n == 0 || s[0] == '0') return 0; // some bad case
vector<int> dp(n + 1, 1);
for (int i = 2; i <= n; ++i) {
int cur = s[i - 1] - '0', pre = s[i - 2] - '0';
if (cur == 0) { // if cur is 0, it must combine with the pre, it can not be alone
if (pre == 0 || pre > 2) return 0; // here is the illegal combine
dp[i] = dp[i - 2]; //if it is legal, it does not add any combination
} else {
dp[i] = dp[i - 1]; // be alone
int two = pre * 10 + cur; // combine with the pre
if (two <= 26 && pre != 0) dp[i] += dp[i - 2]; // if it is legal combine, it add a combination
}
}
return dp[n];
}
};
```