给你一个只包含 '('
和 ')'
的字符串,找出最长有效(格式正确且连续)括号子串的长度。
示例:
输入:s = ")()())"
输出:4
解释:最长有效括号子串是 "()()"
解析:
方法一:动态规则
我们定义dp[i] 表示以下标 i 结尾的最长有效括号的长度。
将dp数组全初始化为0.
显然,有效的子串一定以 ) 结尾,因此我们可以知道以 ( 对应的dp一定为0。
我们只需要求 ) 在dp数组中对应位置的值。
我们从前往后遍历字符串求解dp值,我们每两个字符检查一次:
1. s [ i ] = ')' 且 s[ i-1 ] = '(' ,也就是形如 “...()”, 可推断出: dp [ i ] = dp[ i-2 ] + 2
我们可以理解,因为结束部分的 () 是一个有效字符串,并且将之前的有效字符串的长度增加了 2 。
2. s [ i ] = ')' 且 s[ i-1 ] = ')' , 即形如 “...))” , 可以推断出:
如果 s [ i-dp[i-1] -1 ] = '(' , 那么 dp[ i ] = dp[ i-1 ] + dp[ i - dp[i-1] - 2] + 2
我们可以理解,dp[i-1] 表示 i-1 位置的有效长度, i - dp[i-1] -1 表示跟 i 减去有效长度后前一个位置的字符与 i 相比是否是有效的,即是否为 ( 。
如果是,则表示 i 位置也有效,则 i 位置的有效长度 为 i-1位置的有效长度(dp[i-1]) + 2,然后再加上,这些有效位置的前一个位置的有效长度,
即 dp [ i-dp[ i-1 ] -2 ] 。
如下图
代码如下:
public class leetcode32 {
public static void main(String[] args) {
// TODO Auto-generated method stub
String s = ")()())";
System.out.println(longestValidParentheses(s));
}
//动态规划
public static int longestValidParentheses(String s) {
int maxans = 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-dp[i-1]>0&&s.charAt(i-dp[i-1]-1)=='('){
dp[i] = dp[i-1]+(i-dp[i-1]>=2?dp[i-dp[i-1]-2]:0)+2;
}
}
maxans = Math.max(maxans, dp[i]);
}
return maxans;
}
}
方法二:栈
具体做法是我们始终保持栈底元素为当前已经遍历过的元素中「最后一个没有被匹配的右括号的下标」,这样的做法主要是考虑了边界条件的处理,栈里其他元素维护左括号的下标:
如果栈为空,说明当前的右括号为没有被匹配的右括号,我们将其下标放入栈中来更新我们之前提到的「最后一个没有被匹配的右括号的下标」 如果栈不为空,当前右括号的下标减去栈顶元素即为「以该右括号为结尾的最长有效括号的长度」
我们从前往后遍历字符串并更新答案即可。
需要注意的是,如果一开始栈为空,第一个字符为左括号的时候我们会将其放入栈中,这样就不满足提及的「最后一个没有被匹配的右括号的下标」,为了保持统一,我们在一开始的时候往栈中放入一个值为 −1 的元素。
例如:( ) ) ( ( ( ) )
代码如下:
public int longestValidParentheses(String s) {
int maxans = 0;
Deque<Integer> stack = new LinkedList<Integer>();
stack.push(-1);
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == '(') {
stack.push(i);
} else {
stack.pop();
if (stack.empty()) {
stack.push(i);
} else {
maxans = Math.max(maxans, i - stack.peek());
}
}
}
return maxans;
}