68 ms fast python solution (beat 97%), only put starting '(' index in stack. Detailed explaination


  • 8
    E
    class Solution(object):
        def longestValidParentheses(self, s):
            """
            :type s: str
            :rtype: int
            """
            result=0
            stk=[]
            lst=-1
            for i in xrange(len(s)):
                if s[i]=='(':
                    if lst!=-1:
                        stk.append(lst)
                        lst=-1
                    else:
                        stk.append(i)
                else:
                    if stk:
                        stt=stk.pop()
                        if i-stt+1>result:
                            result=i-stt+1
                        lst=stt
                    else:
                        lst=-1
            return result
    

    stk store the index of '('.

    we intereate through the string.

    result is the length of the longest unbroken bracket chain at that position, we update it when we iterate through the string. We initiate it to 0.

    lst is -1 or the starting index of the unbroken bracket chain we just extended with a matching ')', its initial value is -1, if we iterate to a '(' or a umatchable ')', we set lst to -1. So we are using lst for two purposes.

    Every time we see a '(', we push a index to the stack. if the lst is not -1 (means last time we just got a matching ')' and extended the current unbroken bracket chain and we set lst to the starting index of that chain), we push lst into the stack. If lst is -1, it means we are on index 0 or last character is not a match ')'. We push the index i into the stack. We set lst to -1 in either case.

    Every time we see a ')' and the stack is not empty ( means it's a matching ')' ),we pop the stack. we calculate the length of the chain and update the result and set the lst to the popped index. If the stack is empty, it means that's a unmatchable ')', and we set lst to -1.

    A lot of times, we pop a index and push it right back like when we iterate to index 2 of string "()()"
    In the end of the interation we will have the length of the longest chain in the result variable

    Let me know if the explaination doesn't make sense or hard to understand. I will try my best to revise it.


  • 0
    D
    This post is deleted!

  • 0
    D

    Can you explain your code please? Too often there are beautifully written solutions without clear explanations of the thought process and the steps to coming to their solution


  • 0
    E

    I added description on the solution. Let me know what you think.


  • 0
    D

    Beautiful!!!! Thank you!


  • 0
    R

    Nice solution. Thanks for the explanation. I'm not clear with just one point. Why do we need to set list = -1 in either case, when we encounter an open bracket?


  • 0
    E

    lst(last) is -1 or the starting index of the unbroken bracket chain we just extended with a matching ')', so if we just encounter a '(' , we didn't extend the unbroken bracket chain, so we need to set lst as -1 no matter lst was -1 or not.


  • 0
    E

    I move the "lst=-1" under the condition where lst was not -1. This is more straightforward. Thanks for pointing it out.


  • 0

    Good job. Concise and fast. I implemented a similar idea but was struggling to finish it and then gave up this idea.


  • 0
    X

    You are so brilliant


  • 0

    DP beat 99.88%

    class Solution(object):
        def longestValidParentheses(self, s):
            # dp solution
            dp = [0] * len(s)
            result = leftCount = 0
            for i in range(len(s)):
                if s[i] == '(':
                    leftCount += 1
                elif leftCount > 0:
                    dp[i] = dp[i - 1] + 2
                    dp[i] += (dp[i - dp[i]] if i >= dp[i] else 0)
                    result = max(result, dp[i])
                    leftCount -= 1
            return result
    

Log in to reply
 

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