Leetcode32. 最长有效括号

题目描述

给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。

示例 1：

1
2
3
输入：s = "(()"
输出：2
解释：最长有效括号子串是 "()"

示例 2：

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

示例 3：

1
2
输入：s = ""
输出：0

提示：

  • 0≤s.length≤3×1040 \leq s.length \leq 3 \times 10^4​
  • s[i] 为 '(' 或 ')'

解题思路

方法一：动态规划

算法描述

这道题有”最长“两个字，而且又是字符串，首先考虑一下能不能用动态规划来求解。

定义dp[i]表示以下标i处字符为结尾的最长有效括号的长度。那么我们很容易知道，以(结尾的字串的对应dp数组的值为0，我们只需要求解以)结尾的字串对应的dp数组的值。为了方便，我们可以初始化dp数组为0。

以)结尾的子串有以下情况：

  1. s[i]=')' \mbox{并且} s[i-1]='('​​​​​​​，也就是形如......()的字符串，这样我们很容易得出：

dp[i]=dp[i−2]+2dp[i]=dp[i-2]+2

这个表达式的意思是，最后的字符串()是一个有效的字符串，所以这个字符串最后的有效长度应该是()之前的最后一个字符为结尾的字符串的有效长度再加上2。

  1. s[i]=')' \mbox{并且} s[i-1]=')'​，也就是​形如......))的字符串。这种情况比较复杂，我们可以这样考虑：

如果s[i−dp[i−1]−1]=′(′s[i-dp[i-1]-1]='('，那么

dp[i]=dp[i−1]+dp[i−dp[i−1]−2]+2dp[i]=dp[i-1]+dp[i-dp[i-1]-2]+2

我们考虑如果倒数第二个)是一个有效字符串的一部分（这个字符串可以记作sub），如果对于最后一个)，在倒数第二个)所在的有效字符串的前面还有一个与之对应的(，那么有效字符串的长度就会在倒数第二个)所在的有效字符串长度dp[i-1]的基础上增加2。并且，如果在字符串(sub)之前的最后一个字符为结尾的字符串也有有效字符串的话，还要加上最大的有效字符串长度，也就是dp[i-dp[i-1]-2]。

最后的答案就是dp数组中的最大值。

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int longestValidParentheses(string s){
    int n = s.size();
    vector<int>dp(n,0);

    int ans = 0;
    for(int i = 1;i < n;++i){
        if(s[i] == ')'){
            if(s[i-1] == '('){
                dp[i] = (i >= 2 ? dp[i-2] : 0) + 2;
            }else if(i - dp[i-1] > 0 && s[i-dp[i-1]-1] == '('){
                dp[i] = dp[i-1] + (i-dp[i-1] >= 2 ? dp[i-dp[i-1]-2] : 0) + 2;
            }
        }
        ans = dp[i] > ans ? dp[i] : ans;
    }
    return ans;   
}
  • 在编码的过程中，需要格外注意数组不能越界。

在for循环中，为了方便的处理类似s[i-1]这种情况，可以让游标直接从 1 开始遍历，而且不会影响结果。而对于dp[i-2]或者dp[i-dp[i-1]-2]这种情况的处理，可以在加之前加上判断：

1
2
i >= 2 ? dp[i-2] : 0
i-dp[i-1] >= 2 ? dp[i-dp[i-1]-2] : 0

对于s[i-dp[i-1]-1]这种，**既不能在遍历字符串s的时候越界，也不能在遍历dp数组的时候越界！**在处理的时候，在前面需要加上判断i - dp[i-1] > 0。

复杂度分析

时间复杂度：O(n)O(n)

空间复杂度：O(n)O(n)

方法二：栈方法

算法描述

对这道题的括号问题，相信不少人的第一反应是使用栈。通过栈，我们可以在遍历给定字符串的过程中去判断到目前为止扫描的子串的有效性，同时能得到最长有效括号的长度。

具体做法是我们始终保持栈底元素为当前已经遍历过的元素中「最后一个没有被匹配的右括号的下标」，这样的做法主要是考虑了边界条件的处理，栈里其他元素维护左括号的下标：

  • 对于遇到的每个( ，我们将它的下标放入栈中；
  • 对于遇到的每个 ) ，我们先弹出栈顶元素表示匹配了当前右括号：
    • 如果栈为空，说明当前的右括号为没有被匹配的右括号，我们将其下标放入栈中来更新我们之前提到的「最后一个没有被匹配的右括号的下标」；
    • 如果栈不为空，当前右括号的下标减去栈顶元素即为「以该右括号为结尾的最长有效括号的长度」，我们从前往后遍历字符串并更新答案即可。

需要注意的是，如果一开始栈为空，第一个字符为左括号的时候我们会将其放入栈中，这样就不满足提及的「最后一个没有被匹配的右括号的下标」，为了保持统一，我们在一开始的时候往栈中放入一个值为 −1 的元素。

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int longestValidParentheses(string s){
    stack<int>st;
    int ans=0;

    st.push(-1);
    for(int i=0;i<s.size();++i){
        if(s[i]=='('){
            st.push(i);
        }else{
            st.pop();
            if(st.empty()){
                st.push(i);
            }else{
                ans=i-st.top()>ans?i-st.top():ans;
            }
        }
    }
    return ans;
}

复杂度分享

时间复杂度：O(n)O(n)

空间复杂度：O(n)O(n)

方法三：计数器法

算法描述

在此方法中，我们利用两个计数器 left 和 right 来记录(和)的数量。首先，我们从左到右遍历字符串，对于遇到的每个 ( ，我们增加 left 计数器；对于遇到的每个 ) ，我们增加 right 计数器。然后根据下述规则进行判断：

  • 当 left=rightleft = right时，我们计算当前有效字符串的长度，并且记录目前为止找到的最长子字符串的长度；
  • 当 right>leftright>left​时，我们将 left 和 right 计数器同时变回 0；

这个算法的思想就是当右括号数量多于左括号数量的时候之前的字符我们都扔掉不再考虑，重新从下一个字符开始计算。但这样会漏掉一种情况，就是遍历的时候左括号的数量始终大于右括号的数量，比如((() ，这种时候最长有效括号是求不出来的。

解决的方法也很简单，我们只需要逆着从右往左遍历用类似的方法计算即可，只是这个时候判断条件反了过来：

  • 当 left=rightleft = right时，我们计算当前有效字符串的长度，并且记录目前为止找到的最长子字符串的长度；
  • 当 left>rightleft>right​​​时，我们将 left 和 right 计数器同时变回 0；

这样我们就能涵盖所有情况从而求解出答案。

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
int longestValidParentheses(string s){
    int left=0,right=0,ans=0;
    for(int i=0;i<s.size();++i){
        if(s[i]=='('){
            left++;
        }else{
            right++;
        }
        if(left==right){
            ans=2*right>ans?2*right:ans;
        }else if(right>left){
            left=right=0;
        }
    }

    left=right=0;
    for(int i=s.size()-1;i>0;--i){
        if(s[i]=='('){
            left++;
        }else{
            right++;
        }
        if(left==right){
            ans=2*left>ans?2*left:ans;
        }else if(left>right){
            left=right=0;
        }
    }

    return ans;
}

复杂度分析

时间复杂度：O(n)O(n)

空间复杂度：O(1)O(1)