题解 | #最长的括号子串#

最长的括号子串
给出一个仅包含字符'('和')'的字符串，计算最长的格式正确的括号子串的长度。
对于字符串"(()"来说，最长的格式正确的子串是"()"，长度为2.
再举一个例子：对于字符串")()())",来说，最长的格式正确的子串是"()()"，长度为4.

示例
输入：s = ")()())"
输出：4
解释：最长有效括号子串是 "()()"

方法一：动态规划

由题意可得题目所要求的是"最长"合法括号序列,可以推断出可以动态规划来实现。首先我们设一个一维数组dp[i],其中i代表当选取了第i个字符时最长的合法括号子串长度,之后再分类讨论一下。

对于取到第i位为左括号"("时,dp[i]设置为0,因为取到左括号时这一段的序列一定不是合法的因为多出了一个左括号
对于第i为右括号")"时,有两种情况:
一. 第 i - 1位为左括号"("时，dp[i]可以直接设置成2因为当前括号这一小段为合法,并且判断i - 2处是否有值如果有说明这是一段连续第合法序列即加上i - 2处的dp值.

二. 第i - 1为不为左括号时,说明 i - 1处是合法序列,那么我们需要找到该序列更前面的一个单一左括号, 因为合法序列之间一定存在多出的符号,那么我们只需要找到i - 1位合法序列前不合法序列的倒数第一个符号是否为左括号即可,如果是则将当前值加上2 + dp[i - 1],之后再判一下第i - dp[i - 1] - 2位是否属于一个合法序列,如果是则加上

代码

int dp[40000];
    int longestValidParentheses(string str) {
        // write code here
        int n = str.length();
        int ans = 0;
        for(int i = 1; i < n; i ++){
            //如果第i位为左括号的话直接不进行操作dp[i]默认为0
            if(str[i] == ')'){
                if(i - dp[i - 1] - 1 >= 0 && str[i - dp[i - 1] - 1] == '('){    //将上述两情况合为一种,当i - 1位位左括号时,dp[i - 1]一定为0
                    dp[i] += dp[i - 1] + 2;
                    if(i - dp[i - 1] - 2 >= 0) dp[i] += dp[i - dp[i - 1] - 2];    //找到对应左括号的前一位
                }
            }
            ans = max(ans, dp[i]);
        }
        return ans;
    }

复杂度分析
时间复杂度: O(n) 只需要遍历一遍字符串的长度,也就是n
空间复杂度: O(n) 需要开一个长度为n的dp数组

方法二:正反贪心取

对于一个符号序列，我们可以设定两个计数ls和rs分别代表取到第i位时前有多少个左括号和右括号。每次左括号与右括号相等时计算一次最大值,当序列是从左边开始遍历时如果右括号大于左括号即可清空计数器，当序列从右往前遍历时反之。序列需要从右边再次遍历一次是因为单单从左边遍历会缺少一种条件的判断 "((()()",因为左括号会一直与又括号不相等，所以反过来逆序遍历一遍.
代码

int longestValidParentheses(string str) {
        int ls = 0, rs = 0;
        int n = str.length();
        int ans = 0;
        for(int i = 0; i < n; i ++){ //正序遍历一遍
            if(str[i] == '(') ls++;
            else rs ++;
            if(ls == rs) ans = max(ans, ls * 2); //如果左括号与右括号数量相等则说明当前序列是合法的并更新答案
            else if(rs > ls) ls = rs = 0;
        }
        ls = rs = 0;
        for(int i = n - 1; i >= 0; i --){    //逆序遍历一遍
            if(str[i] == '(') ls ++;
            else rs ++;
            if(ls == rs) ans = max(ans, ls * 2);   //与正序一致
            else if(rs < ls) ls = rs = 0;
        }
        return ans;
    }

复杂度分析
时间复杂度: O(n) 正反两次遍历总长度为2n,忽略常数所以为O(n)
空间复杂度: O(1) 只需要创建若干个变量