2021-07-03：给定一个只由左括号和右括号的字符串，返回最长的有效括号子串的长度。
福大大 答案2021-07-03：
1.正向反向。时间复杂度：O(N)。空间复杂度：O(1)。
用栈的思想。遇到(，left加1；遇到)，right加1。这个容易想到。
只有当left==right的时候，才统计长度。这个很难想到。
先正向求出长度，然后反向求出长度。这个很难想到。
2.动态规划。时间复杂度：O(N)。空间复杂度：O(N)。
代码用golang编写。代码如下：
代码语言：txt复制package main
import "fmt"
func main() {
s := "(()()"
//正向反向
ret := longestValidParentheses(s)
fmt.Println("正向反向：", ret)
//动态规划
ret2 := longestValidParentheses2(s)
fmt.Println("动态规划：", ret2)
}
func longestValidParentheses(s string) int {
N := len(s)
if N <= 1 {
return 0
}
return getMax(longestValidParenthesesZheng(s), longestValidParenthesesFan(s))
}
func longestValidParenthesesZheng(s string) int {
N := len(s)
ans := 0
left := 0
right := 0
for i := 0; i < N; i {
if s[i] == '(' {
left
} else {
right
}
if left == right {
ans = getMax(ans, left)
} else if right > left {
left = 0
right = 0
}
}
return ans * 2
}
func longestValidParenthesesFan(s string) int {
N := len(s)
ans := 0
left := 0
right := 0
for i := N - 1; i >= 0; i-- {
if s[i] == '(' {
left
} else {
right
}
if left == right {
ans = getMax(ans, left)
} else if left > right {
left = 0
right = 0
}
}
return ans * 2
}
func getMax(a int, b int) int {
if a > b {
return a
} else {
return b
}
}
// s只由(和)组成
// 求最长有效括号子串长度
func longestValidParentheses2(s string) int {
if len(s) < 2 {
return 0
}
// dp[i] : 子串必须以i位置结尾的情况下，往左最远能扩出多长的有效区域
dp := make([]int, len(s))
// dp[0] = 0; （ ）
pre := 0
ans := 0
for i := 1; i < len(s); i {
if s[i] == ')' {
// 当前谁和i位置的)，去配！
pre = i - dp[i-1] - 1 // 与str[i]配对的左括号的位置 pre
if pre >= 0 && s[pre] == '(' {
if pre > 0 {
dp[i] = dp[i-1] 2 dp[pre-1]
} else {
dp[i] = dp[i-1] 2
}
}
}
ans = getMax(ans, dp[i])
}
return ans
}执行结果如下：
图片左神java代码
