Longest Valid Parentheses

Question

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.

Tags

• Stack
• Dynamic Programming

Thought

Use stack to store the index of the left parenthesis and the DP table to store the maximum length of the valid parenthesis when containing the current character at the index. Then the maximum value of the DP table is the result.

Code

class Solution(object):
    def longestValidParentheses(self, s):
        """
        :type s: str
        :rtype: int
        """
        # use DP + stack
        l = len(s)
        if l == 0:
            return 0
        dp = [0 for _ in xrange(l)]
        stack = []
        for i in xrange(l):
            if s[i] == '(':
                stack.append(i)
            elif stack == []:
                continue
            else:
                x = stack.pop()
                if x > 0:
                    dp[i] = (i - x + 1) + dp[x - 1]
                else:
                    dp[i] = i - x + 1
        return max(dp)