32. Longest Valid Parentheses

Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring.

For "(()", the longest valid parentheses substring is "()", which has length = 2.

Another example is ")()())", where the longest valid parentheses substring is "()()", which has length = 4.

分析

brute force

写一个判断字符串 s 是否是有效括号对的函数，然后遍历所有的字符子串，并验证，找出最长的。

时间复杂度: 遍历所有子串，O(n²),验证O(n),总的复杂度O(n³)

空间复杂度：O(n)的stack大小

DP

维护一个一位数组dp,dp[i] 代表以s[i]作为结尾的最长有效括号对长度。

当s[i] == '('，dp[i] 一定是0

当s[i] == ')'：

1. s[i-1] == '('，即在尾部出现了‘()’，则dp[i] = dp[i-2] + 2

2. s[i-1] == ')'，即在尾部出现了‘))’

如果 s[i-dp[i-1]-1] == '('，那么 dp[i] = dp[i-1] + 2 + dp[i-dp[i-1]-2]，这里需要把由位置 i-dp[i-1]-1 的‘(’隔断的括号对连上，一起计算。

时间复杂度 O(n)，扫描一次字符串

空间复杂度 O(n)，填充长度为s.size()的一维数组

class Solution {
public:
    int longestValidParentheses(string s) {
        int len = s.size();
        vector<int> dp(len,0);
        int max = 0;
         
        for(int i = 1; i < len; ++i){
           if(s[i] == ')'){
               if(s[i-1] == '('){
                   dp[i] = (i>=2? dp[i-2]:0) + 2;
               }
               else{
                   if(i - dp[i-1] - 1>=0 && s[i - dp[i-1] - 1] == '('){
                       dp[i] = dp[i-1] + 2 + ((i - dp[i-1] - 2) > 0?dp[i - dp[i-1] - 2]: 0);
                   }
               }//--end of else
           }//--end of if
           max = max < dp[i]? dp[i]: max;
        }//--end of for
         
        return max;
    }
};

null