My 80ms Python solution use two stack


  • 0
    H
    class Solution:
    # @param s, a string
    # @return an integer
    def longestValidParentheses(self, s):
        stack,index_stack = [],[-1]
        max_len = 0
        for i in range(len(s)):
            if s[i] == '(':
                stack.append(s[i])
                index_stack.append(i)
            else:
                if stack != []:
                    stack.pop()
                    index_stack.pop()
                else:
                    index_stack.append(i)
        if len(index_stack) == 1:
            max_len = len(s)
        else:
            index_stack.append(len(s))
            for i in range(len(index_stack)-1):
                if index_stack[i+1] - index_stack[i] != 1:
                    if max_len < index_stack[i+1] - index_stack[i] -1:
                        max_len = index_stack[i+1] - index_stack[i] -1
        return max_len

Log in to reply
 

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