题目
题目链接
题解
class Solution {
/**
* 设s[i]为该字符串中第i + 1个字符，即i从0开始
* 设dp[i]为到下标为i为止，有多长有效括号
* 转移方程：
* / dp[i - 2] + 2, s[i] == ')' && s[i - 1] = ='('
* dp[i] = | dp[i - 1] + dp[i - dp[i - 1] - 2] + 2, s[i] == ')' && s[i - 1] == ')' && s[i - dp[i - 1] - 1] == '('
* \ 0, other
*/
public int longestValidParentheses(String s) {
int max = 0;
if (s == null || s.length() == 0) {
return max;
}
int[] dp = new int[s.length()];
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == ')' && i >= 1) {
if (s.charAt(i - 1) == '(') {
if (i - 2 >= 0) {
dp[i] = dp[i - 2] + 2;
} else {
dp[i] = 2;
}
} else if (s.charAt(i - 1) == ')') {
if (i - dp[i - 1] - 1 >= 0 && s.charAt(i - dp[i - 1] - 1) == '(') {
dp[i] = dp[i - 1] + 2;
if (i - dp[i - 1] - 2 >= 0) {
dp[i] += dp[i - dp[i - 1] - 2];
}
} else {
dp[i] = 0;
}
}
} else {
dp[i] = 0;
}
if (max < dp[i]) {
max = dp[i];
}
}
return max;
}
}