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