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.

这道题是LeetCode通过率最低的DP类型题了，但实际上它难度不如正则表达式那两道题，也没有什么需要特殊的预处理，属于少见的O(n)时间复杂度的动态规划，这里自己的解法是完全DP的解法，即利用判断左右括号直接找之前结果里面的对应解，下面是状态方程

if s[i] == '(':
    dp[i] = 0
if s[i] == ')' and s[i - 1] == '(':
    dp[i] = dp[i - 2] + 1
if s[i] == ')' and s[i - 1] == ')':
    if s[i - dp[i - 1] - 1] == '(':
        dp[i] = dp[i - 1] + dp[i - dp[i - 1] - 2] + 1     # 第一个是把和自己属于的括号对算进去，第二个是把相邻的括号对算进去

下面是代码

class Solution(object):
    def longestValidParentheses(self, s):
        """
        :type s: str
        :rtype: int
        """
        n = len(s)
        res = [0] * (n + 1)

        for i in xrange(1, n + 1):
            if s[i - 1] == '(':
                res[i] = 0
            elif i == 1:
                res[i] = 0
            elif s[i - 2] == '(':
                res[i] = res[i - 2] + 1
            elif s[i - 2] == ')':
                if i - 2 * res[i - 1] - 2 >= 0 and s[i - 2 * res[i - 1] - 2] == '(':
                    res[i] = res[i - 1] + 1 + res[i - 2 * res[i - 1] - 2]

        return max(res) * 2

另外是用stack的方法，这种方法不太好描述，总体来说就是现在栈中放入一个-1，每次碰到左括号压入，碰到右括号先弹出，如果弹出之后栈为空，则把当前的下标压入，如果当前栈不为空，则取max length和i - stack.peek()的最大值，因为右括号时先弹出再处理，所以保证了栈中不可能有超过一个右括号的下标存在

class Solution(object):
    def longestValidParentheses(self, s):
        """
        :type s: str
        :rtype: int
        """
        stack = [-1]
        n = len(s)
        max_length = 0
        for i in xrange(n):
            if s[i] == '(':
                stack.append(i)
            else:
                stack.pop()
                if not stack:
                    stack.append(i)
                else:
                    max_length = max(max_length, i - stack[-1])
        return max_length

还有一种O(1)的方法，需要扫描两边完成