LeetCode：32. Longest Valid Parentheses(最长的有效匹配串)

刺骨的言语ヽ痛彻心扉 2022-04-04 14:27 107阅读 0赞

> **文章最前**： 我是Octopus，这个名字来源于我的中文名--章鱼；我热爱编程、热爱算法、热爱开源。所有源码在我的个人[github][] ；这博客是记录我学习的点点滴滴，如果您对 Python、Java、AI、算法有兴趣，可以关注我的动态，一起学习，共同进步。

**相关文章：**

1.  **[LeetCode：55. Jump Game（跳远比赛）][LeetCode_55. Jump Game]**
2.  **[Leetcode：300. Longest Increasing Subsequence（最大增长序列）][Leetcode_300. Longest Increasing Subsequence]**
3.  **[LeetCode：560. Subarray Sum Equals K（找出数组中连续子串和等于k][LeetCode_560. Subarray Sum Equals K_k]**

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

**文章目录**

题目描述：

java实现方法1：

python实现方式1:

java实现方式2:

python实现方式2：

源码github地址：https://github.com/zhangyu345293721/leetcode

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

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

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

示例 1:

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

示例 2:

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

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

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

在此方法中，我们利用两个计数器 left 和 right 。首先，我们从左到右遍历字符串，对于遇到的每个 ‘(’，我们增加 left 计数器，对于遇到的每个 ‘)’ ，我们增加 right 计数器。每当 left 计数器与 right 计数器相等时，我们计算当前有效字符串的长度，并且记录目前为止找到的最长子字符串。当 right 计数器比 left 计数器大时，我们将 left 和 right 计数器同时变回 0。

这样的做法贪心地考虑了以当前字符下标结尾的有效括号长度，每次当右括号数量多于左括号数量的时候之前的字符我们都扔掉不再考虑，重新从下一个字符开始计算，但这样会漏掉一种情况，就是遍历的时候左括号的数量始终大于右括号的数量，即 (() ，这种时候最长有效括号是求不出来的。

解决的方法也很简单，我们只需要从右往左遍历用类似的方法计算即可，只是这个时候判断条件反了过来：

当left 计数器比 right 计数器大时，我们将left 和 right 计数器同时变回 0  
        当 left 计数器与 right 计数器相等时，我们计算当前有效字符串的长度，并且记录目前为止找到的最长子字符串。

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

### java实现方法1： ###

/**
         * 最长有效括号
         *
         * @param s 输入字符串
         * @return 最长数
         */
        public int longestValidParentheses(String s) {
            int left = 0, right = 0, maxlength = 0;
            for (int i = 0; i < s.length(); i++) {
                if (s.charAt(i) == '(') {
                    left++;
                } else {
                    right++;
                }
                if (left == right) {
                    maxlength = Math.max(maxlength, 2 * right);
                } else if (right > left) {
                    left = right = 0;
                }
            }
            left = right = 0;
            for (int i = s.length() - 1; i >= 0; i--) {
                if (s.charAt(i) == '(') {
                    left++;
                } else {
                    right++;
                }
                if (left == right) {
                    maxlength = Math.max(maxlength, 2 * left);
                } else if (left > right) {
                    left = right = 0;
                }
            }
            return maxlength;
        }

时间复杂度：O(n)

空间复杂度：O(1)

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

### python实现方式1: ###

def get_longest_valid_parentheses(self, s: List[str]) -> int:
            '''
                遍历所有的括号,计算有效字符串
            Args:
                s: 字符串
            Returns:
                匹配字符串长度
            '''
            max_len, left, right = 0, 0, 0
            for i in range(len(s)):
                if s[i] == '(':
                    left += 1
                else:
                    right += 1
                if left == right:
                    max_len = max(max_len, 2 * right)
                if right > left:
                    right, left = 0, 0
            right, left = 0, 0
            for j in range(len(s))[::-1]:
                if s[j] == '(':
                    left += 1
                else:
                    right += 1
                if left == right:
                    max_len = max(max_len, 2 * left)
                if left > right:
                    right, left = 0, 0
            return max_len

时间复杂度：O(n)

空间复杂度：O(1)

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

### java实现方式2: ###

/**
         * 最长有效括号
         *
         * @param s 输入字符串
         * @return 最长数
         */
        public int longestValidParentheses2(String s) {
            int maxPairs = 0;
            int length = s.length();
            int[] dp = new int[length + 1];
            Stack<Character> stack = new Stack<>();
            for (int i = 0; i < length; i++) {
                int index = i + 1;
                char ch = s.charAt(i);
                if (ch == '(') {
                    stack.add(ch);
                } else {  // ch==')'
                    if (!stack.isEmpty()) {
                        stack.pop();
                        int pairs = 1 + dp[i];
                        int prevIndex = index - pairs * 2;
                        if (prevIndex >= 0) {
                            pairs += dp[prevIndex];
                            dp[index] = pairs;
                        }
                    }
                }
            }
            for (int num : dp) {
                if (num > maxPairs) {
                    maxPairs = num;
                }
            }
            return maxPairs*2;
        }

时间复杂度：O(n)

空间复杂度：O(n)

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

### python实现方式2： ###

def get_longest_valid_parentheses2(self, s: List[str]) -> int:
            '''
                遍历所有的括号,计算有效字符串
            Args:
                s: 字符串
            Returns:
                匹配字符串长度
            '''
            length = len(s)
            dp = [0] * (length + 1)
            stack = []
            for i, ch in enumerate(s):
                index = i + 1
                if ch == '(':
                    stack.append(ch)
                else:
                    if stack:
                        stack.pop()
                        pairs = 1 + dp[i]
                        prev_index = index - 2 * pairs
                        if prev_index >= 0:
                            pairs += dp[prev_index]
                            dp[index] = pairs
            return max(dp) * 2

时间复杂度：O(n)

空间复杂度：O(n)

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

### 源码github地址： ###

[GitHub - zhangyu345293721/leetcode: java/python for leetcode][GitHub - zhangyu345293721_leetcode_ java_python for leetcode]

[github]: https://github.com/zhangyu345293721
[LeetCode_55. Jump Game]: https://blog.csdn.net/zy345293721/article/details/84991870
[Leetcode_300. Longest Increasing Subsequence]: https://blog.csdn.net/zy345293721/article/details/84984249
[LeetCode_560. Subarray Sum Equals K_k]: https://blog.csdn.net/zy345293721/article/details/84952201
[GitHub - zhangyu345293721_leetcode_ java_python for leetcode]: https://github.com/zhangyu345293721/leetcode