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
