LeetCode32 最长有效括号

发表于 | 分类于 |
字数统计: 519 | 阅读时长 ≈ 2

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

题意

给你一个只包含 ‘(‘ 和 ‘)’ 的字符串，找出最长有效括号子串的长度。

解法

考虑动态规划，令dp[i]表示以第i个字符为结尾的最长有效子串的长度
显然如果当前字符为’(‘，则dp[i]为0
否则，考虑第i - 1个字符ch，如果ch为’)’，则显然ch只能和当前字符配对
dp[i + 1] = dp[i - 1] + 2;
否则，考虑以ch作为末尾的最长子串的起始前一个k，如果k是’(‘则进行配对
此时还需要考虑k的前一个字符，看是否能形成更长的字符
例如()()，第二个’(‘对应的最长长度应该为4而不是2，此时有状态转移
dp[i + 1] = dp[i] + dp[i - dp[i] - 1] + 2;

这道题还可以用贪心的解法来做，从左往右遍历，left表示左括号数量，right表示右括号数量
如果left和right相等则进行答案的更新
如果right大于left，则显然不能完成配对，将left和right置零重新开始匹配
但这样会错过左括号始终比右括号多的情况，例如((())
所以需要再反向遍历一遍，便可覆盖这种情况

代码

动态规划

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int longestValidParentheses(string s) {
        int n = s.size();
        vector<int> dp(n + 1);
        int ans = 0;
        for (int i = 1; i < n; i++) {
            if (s[i] == ')') {
                if (s[i - 1] == ')' && i - dp[i] - 1 >= 0 && s[i - dp[i] - 1] == '(') {
                    dp[i + 1] = dp[i] + dp[i - dp[i] - 1] + 2;
                }
                else if (s[i - 1] == '(') {
                    dp[i + 1] = dp[i - 1] + 2;
                }
            }
            ans = max(ans, dp[i + 1]);
        }
        return ans;
    }
};

贪心

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 n = s.size();
        int left = 0, right = 0, ans = 0;
        for (int i = 0; i < n; i++) {
            if (s[i] == '(') left++;
            else right++;
            if (left == right) ans = max(ans, left + right);
            else if (left < right) {
                left = right = 0;
            }
        }
        left = right = 0;
        for (int i = n - 1; i >= 0; i--) {
            if (s[i] == '(') left++;
            else right++;
            if (left == right) ans = max(ans, left + right);
            else if (left > right) {
                left = right = 0;
            }
        }
        return ans;
    }
};