前言
随机一题
正文
问题来源
本问题来自leetcode上的32题。
问题描述
给定一个只包含 ‘(‘ 和 ‘)’ 的字符串，找出最长的包含有效括号的子串的长度。
示例 1
输入: "(()"
输出: 2
解释: 最长有效括号子串为 "()"
示例 2
输入: ")()())"
输出: 4
解释: 最长有效括号子串为 "()()"
分析：
func longestValidParentheses(s string) int {
l := len(s)
dp := make([]int,l)
max := 0
for i := 0; i < l; i++ {
if s[i] == '(' {
dp[i] = 0
} else {
if (i>1) && (s[i-1] == '(') {
dp[i] = dp[i-2] + 2
} else if (i>0)&&(i-1>=dp[i-1])&&(s[i-1-dp[i-1]]=='(') {//"()"这种情况可以满足
dp[i] = dp[i-1] + 2
if i - dp[i - 1] - 2 >= 0 {
dp[i] += dp[i - dp[i - 1] - 2]
}
}
}
if dp[i] > max {
max = dp[i]
}
}
return max
}
总结：
结语
不要懒，多看多写。
