心之所向便是光

Leetcode 32.最长有效括号

  • 2021-06-03
  • 作者 Ender
  • 3.25K 字
  • 次阅读

题目描述：

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

示例 1：

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

示例 2：

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

示例 3：

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

提示：

  • $0 <= s.length <= 3 * 10^4$
  • s[i] 为 '(' 或 ')'

链接：

https://leetcode-cn.com/problems/longest-valid-parentheses

题目分析

1.动态规划

  我们用 dp[i] 表示以 s[i] 作为结尾的最长有效括号串长度。则可以得到以下性质，当 s[i] 为 ( 时，dp[i] = 0，这是因为有效的括号串一定是以右括号结尾的。而当 s[i] 为 ) 时最长有效括号串是怎么样的呢？
  假若 s[i-1] 为 (，则我们可以认为这个括号串是 dp[i-2] 的括号串加上了一个 ()，这样的括号串仍然是有效括号串，并且长度增加了2。即有 dp[i] = dp[i-2] + 2。
  假若 s[i-1] 为 )，则 s[i-1] 应该和 dp[i-1] 所表示的部分相匹配，如下图所示。而若 s[i] 能够匹配，则只能是匹配到 s[i-dp[i-1]-1] 为 (，与此同时，dp[i-dp[i-1]-2] 所表示的部分也能一并加入到有效括号串中。最后一共为 dp[i] = dp[i-dp[i-1]-2] + dp[i-1] + 2。

leetcode32.jpg

  而我们所要求的答案，便是 dp 数组中的最大值了。按照上面分析的状态转移公式遍历一次括号串即可。需要注意的是，以上的分析都是默认没有越界的情况，因此实际编写代码时均需要首先对这些下标是否存在进行判断。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int longestValidParentheses(string s) {
        if(s.size() < 2) return 0;

        int maxlength = 0;
        vector<int> dp(s.size(), 0);
        for(int i = 1; i < s.size(); i++){
            if(s[i] == ')'){
                if(s[i-1] == '('){
                    dp[i] = (i-2 >= 0 ? dp[i-2] : 0) + 2;
                }
                else if(i-dp[i-1]-1 >= 0 && s[i-dp[i-1]-1] == '('){
                    dp[i] = ((i-dp[i-1]-2 >= 0) ? dp[i-dp[i-1]-2] : 0) + dp[i-1] + 2;
                }
                maxlength = max(maxlength, dp[i]);
            }
        }
        return maxlength;
    }
};

  时间复杂度：$O(n)$，其中 $n$ 为括号串的长度。因为我们只需要遍历一次字符串并更新 dp 数组即可得到结果。
  空间复杂度：$O(n)$，其中 $n$ 为括号串的长度。即为 dp 数组的大小。

2.括号计数

  通过观察我们可以发现，只要左括号和右括号的数量一致，并且右括号不先于未匹配的左括号出现，换句话说，就是从左往右遍历时，左括号数量总是大于等于右括号数量，这样的括号串一定是有效的，这是因为只存在一种括号。则我们可以只维护两个计数器，分别表示左括号和右括号的数量，从左往右遍历一次字符串，每次遇到左括号就将左括号计数加1；遇到右括号就将右括号计数加1，并且进行以下判断：①若右括号数量等于左括号，则这是有效的括号串，长度为左右括号数量之和。②若左括号数量小于右括号，则说明出现了无法匹配的右括号，此时需要将左右括号的计数都重置为0，也即抛弃之前的部分，重新进行匹配。
  而对于左括号始终多于右括号的情况，例子 (()，我们没有一种状态是左括号数量等于右括号。则我们从右往左遍历，用类似的方法，让左右括号的含义交换即可解决。
  注意左右括号数量不相等时是不能保证有效的，例子 ()(()，这个时候左括号数量 3，右括号数量 2，有效的括号串长度并不是 right*2=4。

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
class Solution {
public:
    int longestValidParentheses(string s) {
        int maxlength = 0;
        int left = 0, right = 0;
        for(int i = 0; i < s.size(); i++){
            if(s[i] == '(') left++;
            else{
                right++;
                if(left == right) maxlength = max(maxlength, left + right);
                else if(left < right) left = right = 0;
            }
        }
        left = right = 0;   // 注意第二次遍历之前不要忘了重置计数器
        for(int i = s.size()-1; i >= 0; i--){
            if(s[i] == ')') right++;
            else{
                left++;
                if(left == right) maxlength = max(maxlength, left + right);
                else if(left > right) left = right = 0;
            }
        }
        return maxlength;
    }
};

  时间复杂度：$O(n)$，其中 $n$ 为括号串的长度。因为我们只需要分别从左和从右遍历两次字符串并更新计数器即可得到结果。
  空间复杂度：$O(1)$。我们只需要常数个变量的空间。

本作品采用 知识共享署名-相同方式共享 4.0 国际许可协议 进行许可
,
最后编辑：2021-07-03