My O(n) AC Code in Python.


  • 0
    R
    def longestValidParentheses_dp2(self,s):
        l=len(s)
        DP=[i for i in range(l)]
        result=0
        stack=[]
        for i in range(l):
            if s[i]=='(':
               stack.append(i) 
            else:
                if stack:
                    last=stack.pop()
                    DP[i]=last
                    if last>1 and DP[last-1]!=last-1:
                        DP[i]=DP[last-1]
            if DP[i]!=i:
                result=max(result,i-DP[i]+1)
        return result

  • 0
    L
    This post is deleted!

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.