0032._longest_valid_parentheses.md

32. Longest Valid Parentheses

难度: Hard

刷题内容

原题连接

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

内容描述

Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring.

Example 1:

Input: "(()"
Output: 2
Explanation: The longest valid parentheses substring is "()"
Example 2:

Input: ")()())"
Output: 4
Explanation: The longest valid parentheses substring is "()()"

解题方案

思路 1 - 时间复杂度: O(N)- 空间复杂度: O(N)******

• 动态规划，参考banananana

1. 用一个dp数组来存放以每个index为结尾的最长有效括号子串长度，例如：dp[3] = 2代表以index为3结尾的最长有效括号子串长度为2
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 - 时间复杂度: O(N)- 空间复杂度: O(N)******

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

class Solution:
    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]] == '(':    
                    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(max_length, cur_length)
            next_index = cur_index
        max_length = max(max_length, next_index)
        return max_length