Skip to content

32. longest-valid-parentheses 最长有效括号

难度: 困难

刷题内容

原题连接

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

内容描述

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

示例 1:

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

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

解题方案

思路 1

  • 动态规划,参考banananana
  • 用一个dp数组来存放以每个index为结尾的最长有效括号子串长度,例如:dp[3] = 2代表以index为3结尾的最长有效括号子串长度为2
  • 很明显dp[i]dp[i-1]之间是有关系的
  • s[i] == ‘(’时,dp[i]显然为0, 由于我们初始化dp的时候就全部设为0了,所以这种情况压根不用写
  • s[i] == ')'时, 如果在dp[i-1]的所表示的最长有效括号子串之前还有一个'('s[i]对应,那么dp[i] = dp[i-1] + 2, 并且还可以继续往前追溯(如果前面还能连起来的话)
class Solution(object):
    def longestValidParentheses(self, s):
        """
        :type s: str
        :rtype: int
        """
        if len(s) == 0:
            return 0
        dp = [0 for i in range(len(s))]
        for i in range(1, len(s)):
            if s[i] == ')':
                left = i - 1 - dp[i-1]
                if left >= 0 and s[left] == '(':
                    dp[i] = dp[i-1] + 2
                    if left > 0: # 这个是判断 left 前面是否能与后面继续连起来
                        dp[i] += dp[left-1]
        return max(dp)

思路 2

每当遇到一个左括号或者是无法成对的右括号,就将它压入栈中,可以成对的括号则从栈中 pop 出。这样栈中剩下的就是无法成对的括号的下标。这时我们可以判断这些下标间的距离来获得最大的成对括号长度。 在这里,我们需要先遍历一遍字符串,再遍历一下非空的堆栈。一定要注意,这里我们遍历的非空的栈存储的是没有匹配上的括号下标,匹配上的我们都已经做了pop 处理。

class Solution(object):
    def longestValidParentheses(self, s):
        """
        :type s: str
        :rtype: int
        """
        stack = []
        for i in range(len(s)):
            if s[i] == ')':
                if stack and s[stack[-1]] == '(':    ## 这里要注意,不能想当然地用s[i-1],因为我们有些下标直接continue了没有存到栈中去
                    stack.pop()
                    continue
            stack.append(i)
        max_length = 0
        next_index = len(s)
        while stack:
            cur_index = stack.pop()
            cur_length = next_index - cur_index - 1
            max_length = max(cur_length, max_length)
            next_index = cur_index
        return max(next_index, max_length)


回到顶部