Python: 15 line ,O(n),and have explaining!


  • 1
    P
         """
        left[x] save the ')' matching most left '(' success 
        if happend  parenthesis matching,
        let '(' is in l,  ')' is in r 
        look left[l-1]
        if left[l-1] is exist
        we can konw the s[l-1] must be a ')',and it was matching before!
        so they can merge!
        so left[r]=left[l-1]
        if left[l-1] is not exist
        we let left[r]=l
        and caculate the maxlen!
        """
        stack=[]
        left={}
        max_len=0
        for i,c in enumerate(s):
            if c=='(':
                stack.append(i)
            elif stack:
                l=stack.pop()
                r=i
                if left.has_key(l-1):
                    left[r]=left[l-1]
                else :left[r]=l
                if r-left[r]+1>max_len:
                    max_len=r-left[r]+1
        
        return max_len

Log in to reply
 

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