using dynamic programming
***
s=’(()(())’
dp[7]=以s[6]为结尾的longest valid parentheses substring 长度
j=7-2-dp[6]=5-2=3
j>0 and s[3]=’(‘
d[7]=d[6]+2+d[3]=2+2+2=6
s=’(())())’
j=7-2-dp[6]=5-2=3
s[3]!=’(‘
d[7]=0
****
class Solution(object):
def longestValidParentheses(self, s):
"""
:type s: str
:rtype: int
"""
if len(s)==0:
return 0
max_len=0
dp=[0]*(len(s)+1)
for i in range(1,len(s)+1):
if s[i-1]=='(':
dp[i]=0
else:
j=i-2-dp[i-1]
if j>=0 and s[j]=='(':
dp[i]=dp[i-1]+2+dp[j]
max_len=max(max_len,dp[i])
else:
dp[i]=0
return max_len
using stack
class Solution(object):
def longestValidParentheses(self, s):
"""
:type s: str
:rtype: int
"""
stack=[]
start=0
max_length=0
for i in range(len(s)):
if s[i]=='(':
stack.append(i)
elif s[i]==')':
if len(stack)==0:
start=i+1
else:
stack.pop()
if len(stack)==0:
max_length=max(max_length,i-start+1)
else:
max_length=max(max_length,i-stack[-1])
return max_length
网友评论