[Leetcode][python]Longest Valid Parentheses

) ( ) ( ( ) ) )
0 0 2 0 0 2 6 0

class Solution(object):
    def longestValidParentheses(self, s):
        """
        :type s: str
        :rtype: int
        """
        if not s:
            return 0
        length = len(s)
        dp = [0 for __ in range(length)]  # [0,0,0,0,0,0]

        for i in range(1, length):
            if s[i] == ")":
                j = i - 1 - dp[i - 1]  # 直接去查找前面的第n位，位移过了dp[i-1]位已经匹配的
                if j >= 0 and s[j] == "(":  # 如果那位是‘（’则可以总数多+2
                    dp[i] = dp[i - 1] + 2
                    if j - 1 >= 0:
                        dp[i] += dp[j - 1]  # 重点，会把这次匹配之前的加进去，例如（）（（））
        return max(dp)

class Solution(object):
    def longestValidParentheses(self, s):
        """
        :type s: str
        :rtype: int
        """
        maxlen = 0
        stack = []
        last = -1
        for i in range(len(s)):
            if s[i]=='(':
                stack.append(i)     # push the INDEX into the stack!!!!
            else:
                if stack == []:
                    last = i
                else:
                    stack.pop()
                    if stack == []:
                        maxlen = max(maxlen, i-last)
                    else:
                        # print i, stack[len(stack)-1]
                        maxlen = max(maxlen, i-stack[len(stack)-1])
        return maxlen