题解 | #最长的括号子串#

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param s string字符串 
# @return int整型
#
class Solution:
    def longestValidParentheses(self , s: str) -> int:
        # write code here
        # 1. loop the string and add the left parenthese into stack: if you pass a right parenthese then 
        # pop one from stack to math this right one. if it has then, length+=2 since it is a pair 
        # if it not has then skipp the length and continue with the loop 
        # "(()"
        # t.e.x stack['(','('] then ), pop one ( from stack and they are matched so length+=2
        # ")()(()()((((((())("  
        #1. [(,] 
        #2. ) len>2
        #3. [(, (]
        #4 matched 4  [(]
        # 5. [(, (]
        #6. mactched 6
        
        # initial DP DP[i] is the max length at index i 
        dp=[0]*len(s)
        maxans=0
        for i in range(1,len(s)):
            if s[i]==')':
                if s[i-1]=='(':
                    if i>=2:
                        dp[i]=dp[i-2]+2
                    else: 
                        dp[i]=2
                else:
                    # then this is type of '...))'
                    if (i-dp[i-1])>0 and s[i-dp[i-1]-1]=='(':
                        if i-dp[i-1] >=2:
                            dp[i] = dp[i-1]+dp[i-dp[i-1]-2] +2
                        else:
                            dp[i] = dp[i-1]+2
                maxans=max(maxans,dp[i])
        return maxans