最长有效括号
给定一个只包含 '('
和 ')'
的字符串,找出最长的包含有效括号的子串的长度。
示例 1: 输入: "(()" 输出: 2 解释: 最长有效括号子串为 "()"
示例 2: 输入: ")()())
" 输出: 4 解释: 最长有效括号子串为 "()()"
思路:
解法1:借助栈
借助栈来求解,需要定义个start变量来记录合法括号串的起始位置,我们遍历字符串,如果遇到左括号,则将当前下标压入栈,如果遇到右括号,如果当前栈为空,则将下一个坐标位置记录到start,如果栈不为空,则将栈顶元素取出,此时若栈为空,则更新结果和i - start + 1中的较大值,否则更新结果和i - 栈顶元素中的较大值。
public int longestValidParentheses(String s) {
int res = 0, start = 0;
Stack<Integer> s = new Stack<>();
for(int i = 0; i < s.length(); i++){
if(s.charAt(i) == '('){
s.push(i);
continue;
}else if(s.charAt(i) == ')'){
if(s.isEmpty()){
start = i + 1;
continue;
}else{
stack.pop();
res = s.isEmpty() ? Math.max(res, i - start + 1) : Math.max(res, i - s.peek());
}
}
}
return res;
}
解法2:动态规划
需用到辅助数组d[s.length()],表示从当前字符开始,到字符串结尾的最长有效括号子串长度(当前字符需为有效括号子串的第一个字符)
解题思路:从字符串结尾往前处理,求辅助数组d[]
当前字符下标为index,若当前字符为左括号'(',判断index+1+d[index+1]位置的字符是否为右括号')',若为右括号,则d[index] = d[index+1]+2,并且判断index+1+d[index+1]+1位置的元素是否存在,若存在,则d[index] += d[index+1+d[index+1]+1](解决上述两个有效括号子串直接相邻的情况)
class Solution {
public int longestValidParentheses(String s) {
if(null == s) return 0;
int len = s.length(), max = 0;
int[] d = new int[len];
for(int index = len-2; index >= 0; index--){
int symIndex = index + 1 + d[index+1];
if('(' == s.charAt(index) && symIndex < len && ')' == s.charAt(symIndex)){
d[index] = d[index+1]+2;
if(symIndex+1 < len){
d[index] += d[symIndex+1];
}
}
max = Math.max(max, d[index]);
}
return max;
}
}
参考:https://blog.csdn.net/weixin_38823568/article/details/80997966