问题
给你一个只包含 '('
和 ')'
的字符串,找出最长有效(格式正确且连续)括号子串的长度。
示例 1:
none
输入:s = "(()"
输出:2
解释:最长有效括号子串是 "()"
示例 2:
none
输入:s = ")()())"
输出:4
解释:最长有效括号子串是 "()()"
示例 3:
none
输入:s = ""
输出:0
思路:动态规划
由于同样是字符串处理问题,我们先考虑动态规划:设置$dp$数组,其中$dp[i]$表示以$s[i]$结尾的最长有效子串长度。显然,当$s[i]=’(‘$时,$dp[i]=0$。接下来考虑$s[i]=’)’$的情况。为了方便后续讨论,记$dp[i-1]=l_{i-1}$。
- 若$s[i-1]=’(‘$,则$s[i-1:i]=()$,它们已经有效,因此只需考虑以$s[i-2]$结尾的最长有效子串,拼接起来即可,即$dp[i]=dp[i-2]+2$;
- 若$s[i-1]=’)’$,则子串$s[i-l_{i-1}:i-1]$一定就是以$s[i-1]$结尾的最长有效子串,那么加上$s[i]=’)’$会怎么样呢?此时需要考虑$s[i-l_{i-1}-1]$了。
- 若$s[i-l_{i-1}-1]=’(‘$,那么子串$s[i-l_{i-1}-1:i]$仍然有效,则只需考虑以$s[i-l_{i-1}-2]$结尾的最长有效子串,即$dp[i]=dp[i-l_{i-1}-2]+l_{i-1}+2$;
- 若$s[i-l_{i-1}-1]=’)’$,那么必然不存在以$s[i]$结尾的非空子串,否则与“子串$s[i-l_{i-1}:i-1]$一定就是以$s[i-1]$结尾的最长有效子串”矛盾,故$dp[i]=0$。
状态转移
综上所述,状态转移方程表述为
代码
c++
class Solution {
public:
int dp[30005];
string S;
int DP(int i) {
if(i < 0) return 0;
if(dp[i] != -1) return dp[i];
if(S[i] == '(') return dp[i] = 0;
// S[i] == ')'
if(S[i-1] == '(') {
return dp[i] = DP(i-2) + 2;
} else {
// ((()()))
int k = DP(i-1);
if(dp[i] = i-k-1 >= 0 && S[i-k-1] == '(') {
return dp[i] = k + 2 + DP(i-k-2);
} else return dp[i] = 0;
}
}
int longestValidParentheses(string s) {
if(s.size() == 0 || s.size() == 1) return 0;
memset(dp, -1 ,sizeof(dp));
S = s;
int i;
dp[0] = 0;
if(s[0] == '(' && s[1] == ')') dp[1] = 2;
else dp[1] = 0;
int ans = max(dp[0], dp[1]);
for(i=2; i<s.size(); i++) {
dp[i] = DP(i);
ans = max(ans, dp[i]);
}
return ans;
}
};