最长有效括号

---

image.png

• 难点在于()()如何匹配前面的连续()，还有(())如何处理

举例：s[i-2]==")" ()([)]=>dp[i]=dp[i-2]+2，还有s[i-1]==")" (())=>dp[i]=2+dp[i-1]

我的思路：利用[value,id]栈维持一个 ((...))的匹配，dp+=该范围前一位的dp值（如果该位是")"的话）。如果该位不是")"那么就计算(...)的值作为dp[i]，

class Solution:
    def longestValidParentheses(self, s: str) -> int:
        stack=[]
        res=0
        dp=[0 for i in range(len(s))]
        for i in range(len(s)):
            if s[i] =="(":
                stack.append([s[i],i])
            else:
                if len(stack)>0:
                    c=stack.pop()
                    if c[0]=="(":
                        if c[1]-1>=0:
                            if s[c[1]-1]==")":
                                # ()(())
                                dp[i]=dp[c[1]-1]+(i-c[1]+1)
                            else:
                                dp[i]=i-c[1]+1
                        else:
                            dp[i]=i-c[1]+1
                        res=max(res,dp[i])
                    else:
                        stack.append(c)
                        stack.append([s[i],i])                        
                else:
                    stack.append([s[i],i])
        return res

同样的思维，抛弃栈利用dp我们可以不用加id添加进数组，利用前一位的dp[i-1]的值跳到对应的匹配位确定是否匹配。

class Solution:
    def longestValidParentheses(self, s: str) -> int:
        if s=="":
            return 0
        dp=[0 for i in range(len(s))]
        for i in range(len(s)):
            if s[i] ==")":
                if i-1>=0:
                    # ()
                    if s[i-1]=="(":
                        if i-2>=0:
                            dp[i]=dp[i-2]+2
                        else:
                            dp[i]=2
                    #))
                    else:
                        if dp[i-1]!=0:
                            if i-1-dp[i-1]>=0 and s[i-1-dp[i-1]]=="(":
                                if i-2-dp[i-1]>=0:
                                    dp[i]=dp[i-2-dp[i-1]]+(dp[i-1]+2)
                                else:
                                    dp[i]=dp[i-1]+2
        return max(dp)