# My c++ 0ms DP solution O(n)

• `````` int n = s.size();
if(n == 0 || s[0] == '0') return 0;
if(n == 1) return 1;
int res = 0,fn_1 = 1,fn_2 = 1;
for(int i = 1;i < n;i++){
int temp = fn_1;
if(isValid(s[i])&&isValid(s[i-1],s[i]))  res+=fn_1+fn_2;
if(!isValid(s[i])&&isValid(s[i-1],s[i])) res+=fn_2;
if(isValid(s[i])&&!isValid(s[i-1],s[i])) res+=fn_1;
if(!isValid(s[i])&&!isValid(s[i-1],s[i]))  return 0;
fn_1 = res;
fn_2 = temp;
res = 0;
}
return fn_1;
}
bool isValid(char a,char b){
return a == '1'||(a == '2' && b <='6');
}
bool isValid(char a){
return a != '0';
}``````

• This post is deleted!

• res+= should be res=

Thanks

• Great code! I slightly changed it as follows:

``````int numDecodings(string s) {
int n = s.size();
if ( n == 0 || s[0] == '0' ) return 0;
if ( n == 1 ) return 1;
int m1 = 1, m2 = 1, num;
for ( int i = 1; i < n; i++ ) {
num = 0;
if ( !isValid(s[i]) && !isValid(s[i-1], s[i]) ) return 0;
if ( isValid(s[i]) ) num = m1;
if ( isValid(s[i-1], s[i]) ) num += m2;
m2 = m1;
m1 = num;
}
return num;
}
``````

• It's 4 ms now on leetcode.
259 / 259 test cases passed.
Status: Accepted
Runtime: 4 ms

• Great idea to use overloading here to simplify the code!

One small improvement of the code is to remove temp variable inside the loop.

• Can I ask you why you initialize the array with `int res = 0,fn_1 = 1,fn_2 = 1;`? In DP, does the first character (if non-zero) have the value of 1 in the DP array since it can be decoded? Could you please give me details as the how the state transitions are working?

• This post is deleted!

• This post is deleted!

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