LeetCode题目32：最长的有效括号

原题描述

+

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

示例 1:

输入: "(()"
输出: 2
解释: 最长有效括号子串为 "()"

示例 2:

输入: ")()())"
输出: 4
解释: 最长有效括号子串为 "()()"

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

思路解析

+

用栈的思路我是没想到，但是有个特点你应该能看出来。

宏观上看，给定的任意序列中，可能包含多组有效括号子串。包含在最长的子串里面的子串，一定也是子问题中最长的子串。

所以，最优子结构，重叠子问题，符合动态规划的场景。

具体地推导如下。

我们开辟一个dp数组记录，存储以 结尾的有效子串的最大长度。因为有效的子串，一定是以')'结尾。所以若 第 个字符并非')'，那么dp[i]=0。下面进行递推。

• 当s[i] == ')'且s[i-1]=='('时： 即对应'......()'的结构出现了。我们把'()'前面的最大有效子串考虑进来，那么

• 当s[i] == ')'且s[i-1] == ')'时：

即对应'........))'的结构，它可能是')))'的结构，也可能是'())'的结构，也可能是'(())'的结构。只有最后一种情况值得我们去计算，因为前两者虽然以')'结尾，但前面没有匹配的'('。

此种情况是s[i-dp[i-1]-1]=='('，画个图就明白了。

这时的dp数组递推也呼之欲出了，下图中a+b+2即dp[i]的值：

a是处于'((....))'整个子串结构之前的部分，长度dp[i-dp[i-1]-2]；

b是被s[i]和s[i-dp[i-1]-1]包着的部分，长度dp[i-1]；

2是s[i]和s[i-dp[i-1]-1]这一对。

写代码时注意边界条件，以及上述两个场景的生效条件。

复杂度分析

+

• 时间复杂度：
• 空间复杂度：

C++参考代码

+

class Solution {
public:
    int longestValidParentheses(string s) {
        std::vector<int> dp(s.size(), 0);
        int max_cnt = 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;
                }
            }
        }

        for (int i = 0; i < dp.size(); ++i) {
            max_cnt = max(max_cnt, dp[i]);
        }

        return max_cnt;
    }
};