Python simple 62ms O(n). with dict. (Beat 98% 2016.11.15)


  • 0
    M

    I used to set s = s.lstrip(')').rstrip('(') but it seems that it takes much longger time.

        def longestValidParentheses(self, s):    
            record = {0:-1}       # position of last count. The init value is -1 for the first count==0.
            maxLen = 0           # max length 
            count = 0               # count. +1 for '(', and -1 for ')'
            for i,c in enumerate(s):
                if c == '(': 
                    count += 1
                    record[count] = i      # overwrite due to the latter ')' can only match this one rather than the '(' before it
                else:
                    count -= 1
                    if count not in record:      # set the record if the count not met before
                        record[count] = i
                    else:
                        maxLen = max(maxLen, i - record[count])     # calc the distance from i to the last seen "count"
            return maxLen
    

Log in to reply
 

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