32. Longest Valid Parentheses:

这题有几个难点，一是得想到用DP来做，我一开始用了stack做了一会，发现不行，要记录不同时候的状态，然后就想着用DP来做，结果折腾了半天，DP做出了一个TLE的版本。DP的想法是依次找，先找到相邻的 () 然后找(xx)中间有两个的，再分为两种情况 “(x” & “x)” 或者 “xx” 是valid，然后再找四个的，也就是(xxxx)，分为这些情况（x&xxx) (xxx & x) xxxx这些如果是valid那么(xxxx)就是valid。不过最后还是TLE了，想法倒是没错，不过时间复杂度变n^2了。

（续。。。）
然后看了答案，发现解法还是用stack，简直是打脸。

想法是记录每个 "("的index到stack里，这个我也想到了，但是不忙着计算当前长度，等到所有的值全部loop 完了，再从stack里依次pop来计算两个pop出来之间的长度。还有一个条件就是如果stack为空，并且cur = ")"的话，把这个index也加到stack里去。

所以事实证明一开始的思路还是可以的，只是当要记录状态的时候，没想到如何用存在stack里的index来记录状态。

class Solution(object):
    def longestValidParentheses(self, s):
        """
        :type s: str
        :rtype: int
        """
        #一开始想的是stack，但是试了几下，发现要记录住之前的状态，然后想着用dp试试
        # dp[i][j] start with index i end with index j if it is valid
        # dp[i][j] is valid only if dp[i+1][j-1] is valid and s[i] == "(" and s[j] == ")"
        dp = [[False for _ in range(len(s))] for _ in range(len(s))]
        
        res = 0
        for i in range(len(s)):
            for j in range(len(s)):
                if i > j:
                    dp[i][j] = True
                if j - i == 1 and s[i] == "(" and s[j] == ")":
                    dp[i][j] = True

        l = 1
        while l < len(s):
            for i in range(len(s)-1):
                j = i+l
                if j < len(s):
                    if s[i] == "(" and s[j] == ")":
                        dp[i][j] = dp[i][j] or dp[i+1][j-1]
                        for k in range(i+1, j-1):
                            dp[i][j] = dp[i][j] or (dp[i][k] and dp[k+1][j])
                        if dp[i][j]:
                            res = max(res, j-i+1)
            l += 2
        
        return res

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