# 0ms C++ solution, bits >96% of submissions

• The idea is to use dynamic programming approach and identify a few key cases:
case-1: when there is no way to decode;
case-2: when S_i=S_i-2
case-3: when S_i=S_i-1
case-4: when S_i=S_i-2 + S_i-1.
I used an additional array, but the code ca be easily modified to avoid any arrays.

``````    int numDecodings(string s) {
int s_size=s.size();
if(s_size<1) return 0;
int i=0;
while(s[i]=='0') i++;
if(i>0) return 0; // cannot be decoded
i=s_size-1;
while(s[i]=='0') i--;
if(s_size-1-i>1) return 0; // cannot be decoded;
vector<int> sum(s_size,0);
sum[0]=1;
if(s[1]=='0' && (s[0]=='0' || (s[0]-'0')>2)) return 0;
sum[1]= (s[1]-'0')>0 && (10*(s[0]-'0')+(s[1]-'0'))<=26 ? 2 : 1;
int pair=0;
for(int i=2; i<s_size; i++)
{
if(s[i]=='0' && (s[i-1]=='0' || (s[i-1]-'0')>2)) return 0; // cannot be decoded
pair=10*(s[i-1]-'0')+(s[i]-'0');
if(pair==10 || pair==20)
{
sum[i]=sum[i-2];
continue;
}
if(pair>26 || s[i-1]=='0')
{
sum[i]=sum[i-1];
continue;
}
sum[i]=sum[i-1]+sum[i-2];
}
return sum[s_size-1];
}
``````

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