给定一个只由左括号和右括号的字符串,返回最长的有效括号子串的长度。
1.正向反向。时间复杂度:O(N)。空间复杂度:O(1)。
用栈的思想。遇到(,left加1;遇到),right加1。这个容易想到。
只有当left==right的时候,才统计长度。这个很难想到。
先正向求出长度,然后反向求出长度。这个很难想到。
2.动态规划。时间复杂度:O(N)。空间复杂度:O(N)。
代码用golang编写。代码如下:
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
}
执行结果如下: