本文共 850 字，大约阅读时间需要 2 分钟。

Difficulty: 困难

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

示例 1:

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

示例 2:

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

Solution

Language: ****

​

class Solution {
   public:    int longestValidParentheses(string s) {
           int max_len = 0,_i = 0,stack = 0;        for (int i=0,n = s.size() ; i

dp 的解法：

class Solution {
   public:    int longestValidParentheses(string s) {
           int n = s.size();        vector
   
     dp(n,0);        int ans = 0;        for(int i = 1; i < n; i++){
               if(s[i] == ')' &&  s[i - 1] == '(') dp[i] = i - 2 >= 0? dp[i - 2] + 2: 2;            if(s[i] == ')'  && s[i - 1] == ')' && i - dp[i - 1] - 1 >= 0 && s[i - dp[i - 1] - 1] == '(') dp[i] = dp[i - 1] + (i - dp[i - 1] - 2 >= 0? dp[i - dp[i - 1] - 2]: 0) + 2;            ans = max(ans, dp[i]);        }        return ans;    }};
   

转载地址：http://xyyzi.baihongyu.com/