class Solution {
private:
int calculate(const string& s, int start, vector<int>& dp) {
if (start == s.length()) {
return 1;
}
if (dp[start] != -1) {
return dp[start];
}
int res;
if (s[start] == '0') {
res = 0;
} else {
res = calculate(s, start + 1, dp);
if (start + 1 < s.length() && stoi(s.substr(start, 2)) <= 26) {
res += calculate(s, start + 2, dp);
}
}
dp[start] = res;
return res;
}
public:
int numDecodings(string s) {
vector<int> dp(s.length(), -1);
return calculate(s, 0, dp);
}
};