C++ O(n) no stack DP solution.


  • 1
    W

    dp[i] means the max length substring end at s[i]

    int longestValidParentheses(string s) {
        int len = s.size(), res=0;
        vector<int> dp(len, 0);
        
        for(int i=1; i<len; i++){
            if(s[i] == '(' || (s[i-1] == ')' && dp[i-1] == 0))
                continue;
            else{
                if(s[i-1] == '('){
                    dp[i] += 2;
                    if(i-2>=0)
                        dp[i] += dp[i-2];
                    res = max(res, dp[i]);
                }else if(s[i-1] == ')' && i-dp[i-1]-1 >=0 && s[i-dp[i-1]-1] == '('){
                    dp[i] = 2 + dp[i-1];
                    if(i-dp[i-1]-2>=0)
                        dp[i] += dp[i-dp[i-1]-2];
                    res = max(res, dp[i]);
                }
            }
        }
        
        return res;
    }

  • 0
    T

    I like this one!


Log in to reply
 

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