原题
给定一个只包含 '('
和 ')'
的字符串,找出最长的包含有效括号的子串的长度。
示例 1:
输入: "(()"
输出: 2
解释: 最长有效括号子串为 "()"
示例 2:
输入: ")()())"
输出: 4
解释: 最长有效括号子串为 "()()"
解法
思想
见代码部分
代码
动态规划解法:
dp[i]
代表截至到某个元素的包含有效括号的子串的最长长度(必须包含该字符)。
那么若s.charAt(i) == '('
,则dp[i]
必为0。若s.charAt(i) == ')'
,分情况:
+ s.charAt(i-1) == '('
,则字符串是...()
的形式,此时的dp[i] == dp[i-2]+2
。
+ s.charAt(i-1) == ')'
,则字符串是...))
的形式,此时要看与s.charAt(i-1)
相匹配的左括号的前一个字符是否为(
,若是,则dp[i] == dp[i-1]+2+dp[prev-1]
,若不是,则dp[i] == 0
。
class Solution {
public int longestValidParentheses(String s) {
int max = 0;
int[] dp = new int[s.length()];
for(int i = 1;i<dp.length;i++){
if(s.charAt(i) != '('){
if(s.charAt(i-1) == '('){
int prev = i>=2?dp[i-2]:0;
dp[i] = prev + 2;
if(dp[i]>max) max = dp[i];
}else{
int prev = i-dp[i-1]-1;
if(prev>=0 && s.charAt(prev) == '('){
dp[i] = dp[i-1]+2 + (prev==0?0:dp[prev-1]);
if(dp[i]>max) max = dp[i];
}
}
}
}
return max;
}
}
栈的解法需要一些精妙的设计,要保证栈底必须有一个元素(始终留下一个最左边没参与匹配的下标在栈内):
public class Solution {
public int longestValidParentheses(String s) {
Stack<Integer> stack = new Stack<>();
stack.push(-1);
int max = 0;
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 {
max = Math.max(max, i - stack.peek());
}
}
}
return max;
}
}
原创文章,作者:彭晨涛,如若转载,请注明出处:https://www.codetool.top/article/leetcode32-%e6%9c%80%e9%95%bf%e6%9c%89%e6%95%88%e6%8b%ac%e5%8f%b7/