32. Longest Valid Parentheses:

這題有幾個(gè)難點(diǎn)，一是得想到用DP來(lái)做，我一開(kāi)始用了stack做了一會(huì)，發(fā)現(xiàn)不行，要記錄不同時(shí)候的狀態(tài)，然后就想著用DP來(lái)做，結(jié)果折騰了半天，DP做出了一個(gè)TLE的版本。DP的想法是依次找，先找到相鄰的 () 然后找(xx)中間有兩個(gè)的，再分為兩種情況 “(x” & “x)” 或者 “xx” 是valid，然后再找四個(gè)的，也就是(xxxx)，分為這些情況（x&xxx) (xxx & x) xxxx這些如果是valid那么(xxxx)就是valid。不過(guò)最后還是TLE了，想法倒是沒(méi)錯(cuò)，不過(guò)時(shí)間復(fù)雜度變n^2了。

（續(xù)。。。）
然后看了答案，發(fā)現(xiàn)解法還是用stack，簡(jiǎn)直是打臉。

想法是記錄每個(gè) "("的index到stack里，這個(gè)我也想到了，但是不忙著計(jì)算當(dāng)前長(zhǎng)度，等到所有的值全部loop 完了，再?gòu)膕tack里依次pop來(lái)計(jì)算兩個(gè)pop出來(lái)之間的長(zhǎng)度。還有一個(gè)條件就是如果stack為空，并且cur = ")"的話，把這個(gè)index也加到stack里去。

所以事實(shí)證明一開(kāi)始的思路還是可以的，只是當(dāng)要記錄狀態(tài)的時(shí)候，沒(méi)想到如何用存在stack里的index來(lái)記錄狀態(tài)。

class Solution(object):
    def longestValidParentheses(self, s):
        """
        :type s: str
        :rtype: int
        """
        #一開(kāi)始想的是stack，但是試了幾下，發(fā)現(xiàn)要記錄住之前的狀態(tài)，然后想著用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