leetcode力扣（32）----------最长有效括号

阳光穿透心脏的1/2处 2023-06-25 06:22 14阅读 0赞

#### 题目描述： ####

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

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

这\*\*里说明一下，不仔细理解，光看用例，很容易理解为 字符串中的有效括号数量。所有很坑!!!\*\*其实是 字符串中有效连续的最大括号数量 \*\*（））（）\*\*这种的话，他的最大有效括号数是2，也就是一对括号。因为开头的一对，与末尾的一对中含有一个单括号，不合法，所以并不是连续的。

##### 解题思路： #####

利用的是动态规划，首先定义状态**DP\[ i \] ：代表以当且字符结尾时的 最长子串长度**。可以推导出动态转移方程：

> if s\[i\]为 ( dp\[i\] = 0  
> \* s\[i\] 为 )  
> \* if s\[i-1\] 为 ( dp\[i\] = dp\[i-2\]+2  
> \* else if s\[i-1\]为 ) 并且 s\[i - dp\[i - 1\] - 1\] 为）// 判断i-1这个结尾的 最长合法字符的前一个 是否跟最后一个字符匹配  
> \* dp\[i\] = dp\[i-1\]+2 +dp\[i-dp\[i-1\]-2\] // 此种情况相当于 …( dp\[i-1\] )…  
> // dp\[i-1\]位期间合法的长度 + 匹配的一对括号长度2 + 靠近dp\[i-1\] 的那个(括号，前面的有效字符串

**代码如下：**

public int longestValidParentheses3(String s) { 
            int res = 0;
            int [] dp = new int [s.length()];
            for (int i =1;i<s.length();i++){ 
                if (s.charAt(i)==')'){ 
                    if (s.charAt(i-1)=='('){ 
                        dp[i] = (i - 2 >= 0 ? dp[i - 2] + 2 : 2);
                    }else if (s.charAt(i - 1) == ')' && i - dp[i - 1] - 1 >= 0 && s.charAt(i - dp[i - 1] - 1) == '(') { 
                        dp[i] = dp[i - 1] + 2 + (i - dp[i - 1] - 2 >= 0 ? dp[i - dp[i - 1] - 2] : 0);
                    }
                }
                res = Math.max(res, dp[i]);
                }
            return res;
            }