Monday, June 9, 2014

LeetCode (Python): Longest Valid Parentheses

Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring.
For "(()", the longest valid parentheses substring is "()", which has length = 2.
Another example is ")()())", where the longest valid parentheses substring is "()()", which has length = 4.

Solution:

class Solution:
    # @param s, a string
    # @return an integer
    def longestValidParentheses(self, s):
        stack = []
        lastError = -1
        longestValidParentheses = 0
        for i in range(0, len(s)):
            if s[i] =='(':
                stack.append(i)
            else:
                if len(stack) == 0:
                    lastError = i;
                else:
                    stack.pop()
                    if len(stack)==0:
                        validTill = lastError
                    else:
                         validTill = stack[-1]
                    longestValidParentheses = max(longestValidParentheses, i-validTill)
        return longestValidParentheses

No comments :

Post a Comment