我的代码居然过了。。
class Solution:
def expand(l,s):
r = False
for item in l:
left = item[0]
right = item[1]
if left>=1 and s[left-1]==‘(‘ and right+1<len(s) and s[right+1]==‘)‘:
item[0] -= 1
item[1] += 1
r = True
return r
def merge(l):
if len(l)<=1:
return l
for i in range(1,len(l)):
if l[i][0]-l[i-1][1]==1:
l[i][0] = -1
l[i-1][1] = -1
nl = []
for item in l:
nl.extend(item)
nl = [i for i in nl if i!=-1]
l = [nl[i:i+2] for i in range(0,len(nl),2)]
return l
def longestValidParentheses(self, s: str) -> int:
if len(s)==1:
return 0
l = []
for i in range(1,len(s)):
if s[i-1]==‘(‘ and s[i]==‘)‘:
l.append([i-1,i])
if len(l)==0:
return 0
while True:
l = Solution.merge(l)
#print(‘merge‘,l)
r = Solution.expand(l,s)
#print(‘expand‘,l)
if not r:
break
l = [i[1]-i[0]+1 for i in l]
return max(l)
我的思路就是模拟，括号肯定是一层一层的，所以我就从最里面一层开始，慢慢往外拓展（expand），如果拓展不了，说明就这些了。然后找到最大的区间就好了。
我的思路基本跟暴力差不多，所以性能很差。
这道题的题目描述有点问题。“找出最长的包含有效括号的子串的长度”容易让人误解，这里的子串实际上指的是连续子串。
看官方题解，给了三种方法。分别是dp，栈和贪心。这三种我都没怎么看懂。。
把链接放下面，什么时候想起来了再去研究研究 https://leetcode-cn.com/problems/longest-valid-parentheses/solution/zui-chang-you-xiao-gua-hao-by-leetcode-solution/
不过第一个dp我觉得解释的似乎有点问题。dp[i]定义的是到i结尾的字符串的最长有效括号的长度。
但是我用题解的代码，跑测试样例"())()"，得到的dp数组为0，2，0，0，2
一共五个括号，中间那个括号，按照dp数组的定义，不应该是2嘛。这里我没相同，是题解有问题还是我没理解对？
原文：https://www.cnblogs.com/digdig/p/13237206.html