题目
给定一个只包含 '(' 和 ')' 的字符串,找出最长的包含有效括号的子串的长度。
示例 1:
输入: "(()"
输出: 2
解释: 最长有效括号子串为 "()"
示例 2:
输入: ")()())"
输出: 4
解释: 最长有效括号子串为 "()()"
解题思路
精疲力尽....连续10个小时,最后还是抄了题解,找转移方程真是太费劲了,自己的解法总是遇到无穷无尽的边界判断,脑子要炸了。
代码
class Solution {
public int longestValidParentheses(String s) {
int maxLength = 0;
int dp[] = new int [s.length()];
for (int i = 1; i < s.length(); i++) {
if (s.charAt(i) == ')'){
if (s.charAt(i - 1) == '('){ //上一个括号可以和当前形成组合
dp[i] = ( i >= 2 ? dp[i - 2] : 0) +2;
}else if(i - 1 - dp[i - 1] >= 0 && s.charAt(i - 1 - dp[i - 1]) == '('){ //排除掉已经计算过的括号后,再判断前一个括号是否可以和当前形成组合,dp[i - 1]代表上一步中已经得知的有效括号长度,减去这个长度后就可方便的得到尚未匹配的那个括号。
dp[i] = dp[i - 1] + ((i -2 - dp[i - 1]) >= 0 ? dp[i -2 - dp[i - 1]]:0) + 2 ;
}
maxLength = Math.max(maxLength, dp[i]);
}
}
return maxLength;
}
}
网友评论