Given a string containing just the characters ‘(‘ and ‘)’, find the length of the longest valid (well-formed) parentheses substring.
For “(()”, the longest valid parentheses substring is “()”, which has length = 2.
Another example is “)()())”, where the longest valid parentheses substring is “()()”, which has length = 4.
左右遍历
func longestValidParentheses(s string) int {
var ret int
var l,r int
for i:=0;i<len(s);i++{
if s[i]=='('{
l++
}else {
r++
}
if l==r{
if 2*r>ret{
ret=2*r
}
}else if r>=l{
l=0
r=0
}
}
l=0
r=0
for i:=len(s)-1;i>0;i--{
if s[i]=='('{
l++
}else {
r++
}
if l==r{
if 2*l>ret{
ret=2*l
}
}else if l>r {
l=0
r=0
}
}
return ret
}
dp
func longestValidParentheses(s string) int {
var ret int
var dp[] int=make([]int,len(s))
for i:=0;i<len(s);i++{
dp[i]=0
}
for i:=1;i<len(s);i++{
if s[i]==')'{
if s[i-1]=='('{
var tmp int
if i-2>0{
tmp=dp[i-2]
}else {
tmp=0
}
dp[i]=tmp+2
}else if i-dp[i-1]>0&&s[i-dp[i-1]-1]=='('{
var tmp int
if i-dp[i-1]-2>0{
tmp=dp[i-dp[i-1]-2]
}else {
tmp=0
}
dp[i]=dp[i-1]+tmp+2
}
if dp[i]>ret{
ret=dp[i]
}
}
}
return ret
}
时间超限
func longestValidParentheses(s string) int {
ret:=0
index:=0
for index<len(s) {
lastlength:=0
arryl:=make([]int,0)
arryr:=make([]int ,0)
for i := index; i < len(s); i++ {
if s[i] == '(' {
arryl = append(arryl, i)
} else if s[i] == ')' {
arryr=append(arryr,i)
if len(arryr)>len(arryl){
break
}
if len(arryl)==len(arryr){
lastlength=i-index+1
}
}
}
if lastlength>ret{
ret=lastlength
}
index++
}
return ret
}