32. 最长有效括号

问题

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

左右括号匹配，即每个左括号都有对应的右括号将其闭合的字符串是格式正确的，比如 "(()())"。

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

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

分析

括号匹配，首先想到用栈，这道题也可以动态规划。主要分为"...()"和"...))"两种情况。

代码

class Solution {
public:int s_n = 0;const static int N = 3e4+10;int f[N];int res = 0;int longestValidParentheses(string s) {s_n = s.size();// ()(())// 1 "...()" f[x] = f[x-2] +2// 2 "...))" f[x] = f[x-1] + f[x-1-dp[x-1]-1]for (int i = 1; i < s_n; i++) {if (s[i] == ')') {if (s[i-1] == '(') {f[i] = (i >= 2 ? f[i-2] : 0) + 2;} else if (i-1-f[i-1] >= 0 && s[i-1-f[i-1]] == '(') {// 这里就是s[i-1-f[i-1]] == '('能与s[i]==')'匹配上f[i] = f[i-1] + ((i-1-f[i-1]) >= 1 ? f[i-1-f[i-1]-1] : 0) + 2;}res = max(res, f[i]);}}return res;}
};