032.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 "()()"

分析

• 本题是一道Hard题目，其基于Valid Parentheses这个概念。
• 有效序列的意思是 所有所有括号都可以相互匹配，符合数学定义。比如：()()、(())、(()())等均符合有效序列的定义。
• 题目给定序列，序列内可能包含多个有效序列，返回最长序列的长度即可。
• 本题目可以扩展为：序列是否为有效问题，具体做法为：如果 返回长度==序列长度，则整个序列为有效序列。

栈实现

• 使用栈这里需要注意题目的要求，我们寻找的是最长的有效括号的长度，所以这是一个寻找连续子子串的问题。
• 所以，为了判断连续的问题，我们在栈中保存每个符号的索引位置i，而不是每个符号的值。
• 通过判断当前匹配右括号和栈弹出元素后的栈顶元素的索引位置，来记录最大匹配长度。

class Solution:
    def longestValidParentheses(self, s: str) -> int:
        if len(s) == 0:
            return 0
        res = 0
        stack = [-1]
        for i in range(len(s)):
            if s[i] == "(":
                stack.append(i)
            else:
                # 里边只有"("
                stack.pop()
                if len(stack):
                    # 上一个多余括号，或者从头开始算
                    res = max(res, i - stack[-1])
                else:
                    # 如果stack是空，且输入')'
                    stack.append(i)
        return res

动态规划

• dp[i]表示以当前位置为终点的最长长度，则只能在）处更新；
• 如果s[i-1-dp[i-1]]==’(‘，则说明当前位置可以和i-1-dp[i-1]位置匹配，dp[i]=dp[i-1]+2;
• 然后还要加上匹配位置之前的最长长度dp[i]+=dp[i-dp[i]];

class Solution:
    def longestValidParentheses(self, s: str) -> int:
        res = 0
        s = ')' + s
        dp = [0 for _ in s]
        for i in range(1, len(s)):
            if s[i] == ')':
                if s[i - 1 - dp[i-1]] == '(':
                    dp[i] = dp[i-1] + 2
                # 比如(()())
                dp[i] += dp[i-dp[i]]
            res = max(res, dp[i])
        return res