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


  • 45
    W
     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';
    }

  • 0
    W
    This post is deleted!

  • 0
    T

    res+= should be res=

    Thanks


  • 3
    A

    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;
    }
    

  • 0
    Y

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


  • 1
    T

    Great idea to use overloading here to simplify the code!

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


  • 0
    R

    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?


  • 0
    L
    This post is deleted!

  • 0
    L
    This post is deleted!

Log in to reply
 

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