Simple Python, beats 95%


  • 1
    M

    '''

    def longestValidParentheses(self, s):
        """
        :type s: str
        :rtype: int
        """
        maxlen = 0
        
        # search forward
        cnt, start = 0, 0 #counting brackets
        for i in xrange(len(s)):
            cnt += (1, -1)[s[i] == ')']
            if cnt == 0 and i - start + 1 > maxlen:
                maxlen = i - start + 1 # update maximum length 
            elif cnt < 0: 
                start, cnt = i + 1, 0 # update start point
        # search backward
        cnt, start = 0, len(s)-1
        for i in xrange(len(s)-1, -1, -1):
            cnt += (1, -1)[s[i] == '(']
            if cnt == 0 and start - i + 1 > maxlen:
                maxlen = start - i + 1
            elif cnt < 0:
                start, cnt = i - 1, 0
        return maxlen
    

    '''


Log in to reply
 

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