一、题目
Given a string containing just the characters ‘(’ and ‘)’, return the length of the longest valid (well-formed) parentheses
substring
.
Example 1:
Input: s = “(()”
Output: 2
Explanation: The longest valid parentheses substring is “()”.
Example 2:
Input: s = “)()())”
Output: 4
Explanation: The longest valid parentheses substring is “()()”.
Example 3:
Input: s = “”
Output: 0
Constraints:
0 <= s.length <= 3 * 104
s[i] is ‘(’, or ‘)’.
二、题解
class Solution {
public:
int longestValidParentheses(string s) {
int n = s.size();
vector<int> dp(n,0);
int res = 0;
for(int i = 1;i < n;i++){
if(s[i] == ')'){
int p = i - dp[i-1] - 1;
if(p >= 0 && s[p] == '('){
dp[i] = dp[i-1] + 2 + (p - 1 >= 0 ? dp[p-1] : 0);
}
}
res = max(res,dp[i]);
}
return res;
}
};
