A simple c++ DP solution without stack, 8ms in 8 lines


  • 4
    R
     1. dp[i] = {max(k) | s[i-k+1, i] is well formed. k=0 means empty}
     2. For char s[i], we should check the char s[i-1-dp[i-1]]. 
      If s[i] and s[i-1-dp[i-1]] are matched, substring from  i-1-dp[i-1] to i is well formed. 
      Then, we should joint it with previous well formed substring which ends at s[i-1-dp[i-1]-1].
    
     int longestValidParentheses(string s) {
                vector<int> dp(s.length(),0);
                int res = 0;
                for(int i=1; i<s.length(); ++i)
                    if(s[i]==')' && i-1-dp[i-1]>=0 &&s[i-1-dp[i-1]]=='('){
                        if(i-1-dp[i-1]-1 >= 0) dp[i]= dp[i-1]+2+dp[i-1-dp[i-1]-1];
                        else  dp[i]= dp[i-1]+2;
                        res = max(res, dp[i]);
                    }
                return res;
            }

Log in to reply
 

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