(Hard) 32. Longest Valid Parentheses

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

题意: 找出 最长有效子字串

有效:

• 先左再右
• 左右形成 one pair
• 如果以stack法(先进後出)判断 最後长度为0

Example 1:

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

Example 2:

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

Example 3:

Input: s = ""
Output: 0

Constraints:

0 <= s.length <= 3 * 104
s[i] is '(', or ')'.

解法:
原本判定 是否有效 以stack 来做的话
丢符号 '(' or ')'进去判别
但这其实是适用判断整串字串

但这题是求子字串的有效和其字串长度,也就是说: 在有效子字串(s)中看谁最长 --> 动态ansMax更新
而切分点 可由
Ex : ()(() : 2 ( 2 --> 切分点为 '('

Hint : 丢 index 进 stack 可用来计算长度

Code

class Solution:
    def longestValidParentheses(self, s: str) -> int:
        stack = []
        stack.append(-1)
        ansMax = 0
        if len(s)==0:
            return 0
        for i in range(len(s)):
            if s[i]=='(':
                stack.append(i)
            else:
                stack.pop()
                if len(stack)==0:
                    stack.append(i)
                else:
                    #print(stack[-1])
                    curlen = i - stack[-1]
                    if curlen > ansMax:
                        ansMax = curlen
        print(ansMax)
        return ansMax