最长有效括号

今天药忘吃喽~ 2022-12-05 10:00 159阅读 0赞

# 最长有效括号 #

## 1、参考资料 ##

https://leetcode-cn.com/problems/longest-valid-parentheses/

## 2、题目要求 ##

> **题目描述**

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

> **示例 1:**

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

> **示例 2:**

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

## 3、代码思路 ##

动态规划

1.  还是老问题：为什么要用动态规划？假如说 `str[i] == ')'`，我们就要往字符串前面去寻找，有没有能匹配该 `')'` 的 `'('`，那么需要往前走多少步？前面的有效括号长度是多少，这都不得而知，所以我们需要以 `str[i]` 结尾的最长有效括号长度记录下来，这样计算以 `str[i]` 结尾的最长有效括号长度时可以直接拿来用
2.  我感觉我摸出套路来了，我们定义 `dp[i]` 的含义为：以 `str[i]` 结尾的最长有效括号长度，对于以 `(` 结尾的字符串，因为 `'('` 无法闭合，所以 `dp[i]` 永远等于 `0`；对于以 `')'` 结尾的字符串，我们还需要分情况判断

--------------------

以 `')'` 结尾的字符串，即 `str[i] == ')'`

1.  如果 `str[i-1] == '('`，则说明与 `'('` 配对的 `'('` 就在其左边，配对成功，但是这样还不行，我们还需要加上 `str[i-2]` 结尾的最长有效括号长度(`dp[i-2]`，当然前提是 `i-2` 不会造成数组越界)，这样才能算是以 `str[i] == ')'` 结尾的最长有效括号长度
2.  如果 `str[i-1] == ')'`，那么我们需要往左去寻找与 `'('` 匹配的 `')'`，因为 `dp[i-1]` 存储的是以 `str[i-1]` 结尾的最长有效括号长度，所以我们需要往左找到 `i-dp[i-1]-1` 的位置，如果 `str[i-dp[i-1]-1] == '('`，则证明匹配成功(前提是 `i-dp[i-1]-1` 没有造成数组越界)，同样，我们还需要加上以 `str[i-dp[i-1]-1-1]` 结尾的最长有效括号长度(`dp[i-dp[i-1]-2]`，当然前提是 `i-dp[i-1]-2` 不会造成数组越界)
3.  当我们知道字符串中所有以 `str[i]` 结尾的最长有效括号长度(`i` 为 `0~str.length-1`)，再从其中选出最大值，即为整个字符串的最长有效括号

## 4、代码实现 ##

代码

class Solution {
        
        public int longestValidParentheses(String str) {
        
            // Guard safe
            if (str == null || str.length() == 0) {
        
                return 0;
            }
    
            int[] dp = new int[str.length()];
            // 单个字符的最长有效括号长度为 0
            dp[0] = 0;
            // 默认最长有效括号长度为 0
            int maxLength = 0;
    
            // 以字符串中每个字符作为结尾，判断以 str[i] 结尾的最长有效括号长度
            for (int i = 1; i < str.length(); i++) {
        
                // 如果以 ')' 结尾，则需要尝试去匹配其左边的 '('
                if (str.charAt(i) == ')') {
        
                    // 如果 ')' 左边紧挨着 '('，则证明匹配成功
                    if (str.charAt(i - 1) == '(') {
        
                        if (i - 2 >= 0) {
        
                            // 如果 i-2 不发生越界，刚配对上的 "()" 长度为 2，再加上以 str[i-2] 结尾的最长有效括号长度
                            dp[i] = dp[i - 2] + 2;
                        } else {
        
                            // 否则 i - 2 < 0，则说明 i = 2，刚配对上的括号为 "()"，长度为 2
                            dp[i] = 2;
                        }
                    } else {
        
                        // 否则，我们需要向左去寻找与其配对的 '('
                        int matchIndex = i - dp[i - 1] - 1;
                        // 如果 matchIndex < 0，则证明之前的括号全部匹配成功，str[i] 是多余的括号
                        // 如果 matchIndex >= 0，则证明之前的括号并未完全匹配，str[i] 还有机会匹配成功
                        if (matchIndex >= 0) {
        
                            // 如果是 '('，则证明配对成功
                            if (str.charAt(matchIndex) == '(') {
        
                                // 如果 matchIndex - 1 < 0，则说明加上 str[i] 后，所有括号都匹配成功
                                // 如果 matchIndex - 1 >= 0，还需要加上以 str[matchIndex - 1] 结尾的最长有效括号长度
                                if (matchIndex - 1 >= 0) {
        
                                    dp[i] = dp[i - 1] + dp[matchIndex - 1] + 2;
                                } else {
        
                                    dp[i] = dp[i - 1] + 2;
                                }
                            }
                        }
                    }
                }
                // 动态记录整个字符串的最长有效括号长度
                maxLength = Math.max(dp[i], maxLength);
            }
            return maxLength;
        }
    }