```
class Solution
{
public:
int numDP(string s, int start, vector<int>& memo)
{
if (start == s.size()) return 1;
if (memo[start] != 0) return memo[start];
int count = 0;
int num = stoi(s.substr(start, 1));
if (num > 0 && num <= 9)
{
count = numDP(s, start+1, memo);
if (start + 2 <= s.size())
{
num = stoi(s.substr(start, 2));
if (num > 0 && num <= 26)
count += numDP(s, start+2, memo);
}
}
memo[start] = count;
return memo[start];
}
int numDecodings(string s)
{
if (s.empty()) return 0;
vector<int> memo(s.size(), 0);
return numDP(s, 0, memo);
}
};
```