Longest Valid Parentheses (Lettc

• 题目 -->传送门
  给定一个字符串s，由 '(' 和 ')' 组成，求最长合法括号(valid parentheses)长度

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

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

官方有示例解答

• 采用 stack 解决
  我们可以在扫描给定的字符串时使用栈，以检查到目前为止扫描的字符串是否有效，以及最长有效字符串的长度。
  1、如果是 ( 则直接将其下标压入栈，因为有效字符串总是 ( 在前
  2、 如果是 ) 先从堆栈中弹出一个元素，(说明可能找到有效字符串了)然后用下标减去栈顶元素，得到的值就是最大有效字符串的长度。如果栈为空，则压入当前下标

 def longestValidParentheses(s):
        """
        :type s: str
        :rtype: int
        """
        stack = [-1]
        max_length = 0
        for i,c in enumerate(s):
            if c == '(':
                stack.append(i)
            else：
                stack.pop()
                if len(stack) == 0:
                    stack.append(i)
                else:
                    max_length = max(max_length, i-stack[-1])
        return max_length

• 采用动态规划
  仔细考虑以下，最长有效子串只能在 ) 出结束，所以有两种情况：
  一、 它前一个字符是 ( ，那么构成一个有效字符串，所以在之前有效字符串长度基础上加 2
  二、 它前一个字符是 ），s[ i − dp[i−1] − 1] = '('，那么构成类似 '(())' 这样的字符串，也是一个有效字符串，那么当前的最大字符串则是
  dp[i] = dp[i−1] + dp[i−dp[i−1]−2] + 2
  不会了，看官方示例有点不懂。