c O(n) dp, easy to understand


  • 0
    M
    int longestValidParentheses(char* s) {
        int slen = strlen(s);
        int ret = 0;
        int *dp = malloc(slen * sizeof(dp[0]));
        
        int i;
        for(i = 0; i < slen; ++i){
            
            if(s[i] == '('){
                dp[i] = 0;
            }else{
                
                if(i > 0){
                    
                    if(s[i-1] == '('){
                        dp[i] = 2;
                    }else{
                        if(i - 1 - dp[i - 1] >= 0 && s[ i - 1 - dp[i - 1] ] == '('){
                            dp[i] = dp[i - 1] + 2;
                        }else{
                            dp[i] = 0;
                        }
                    }
                    
                    if(i - dp[i] >= 0){
                        dp[i] += dp[i - dp[i]];
                    }
                    
                    if(ret < dp[i]){ret = dp[i];}
                }else{
                    dp[i] = 0;
                }
                
            }
        }
        
        return ret;
    }
    

Log in to reply
 

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