# two ways, recursion, much easier to think of but time limited; dynamic programming, the faster and better one

• recursion:

``````class Solution {
public:
int numDecodings(string s) {
if(s == "" || s[0] == '0') return 0;
for(int i=0;i<s.size()-1;++i)
if(s[i] == '0' && s[i+1] == '0')
return 0;
return numDecodings(s,0);
}
private:
int numDecodings(string& s,int cur)
{
if(cur == s.size()) return 1;
if(s[cur] == '0') return 0;
if(cur == s.size()-1) return 1;
if(s[cur] == '1' || (s[cur] == '2' && s[cur+1] <= '6'))
return (numDecodings(s,cur+1) + numDecodings(s,cur+2));
return numDecodings(s,cur+1);
}
};
``````

dynamic programming:

``````class Solution {
public:
int numDecodings(string s) {
if(s == "" || s[0] == '0') return 0;
int size = s.size();
int num[size+1];
num[size] = 1;
if(s[size-1] == '0') num[size-1] = 0;
else num[size-1] = 1;
for(int i=s.size()-2;i>=0;--i)
{
if(s[i] == '0' && s[i+1] == '0')    return 0;
if(s[i] == '0') num[i] = 0;
else if(s[i] == '1' || (s[i] == '2' && s[i+1] <= '6'))
num[i] = num[i+1] + num[i+2];
else
num[i] = num[i+1];
}
return num[0];
}

};``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.