首页 > 代码库 > 【leetcode刷题笔记】Longest Valid Parentheses
【leetcode刷题笔记】Longest Valid Parentheses
Given a string containing just the characters ‘(‘
and ‘)‘
, find the length of the longest valid (well-formed) parentheses substring.
For "(()"
, the longest valid parentheses substring is "()"
, which has length = 2.
Another example is ")()())"
, where the longest valid parentheses substring is "()()"
, which has length = 4.
题解:dp+栈
用一个栈记录左括号的索引,每次匹配到")"的时候,弹出对应的左括号,并且用这个索引计算括号的长度。
用currentMax记录当前最长的匹配串,它可以由多个有效的匹配累加而成,比如"()(())",currentMax = 2 + 4 = 6;或者等于当前最大的匹配,比如"()((())",currentMax = 4;
leftLen表示匹配当前")"时,得到的最长匹配是多少,比如"()(())",leftLen = 4;
totalMax是最终最长的匹配长度,每次匹配到")"的时候更新。
遇到‘(‘,压栈
遇到‘)‘有三种情况:
- 类似"())"或者")"的情况,即这个右括号是多余的,判断的条件是此时栈为空,说明重新开始了,把currentMax置零;
- 类似"()()"或者"()(())"的情况,即这个右括号是匹配的,并且它匹配以后栈空了,说明前面搜索到的"()"可以和当前搜索完的串"()"或者"(())"合并起来,把currentMax += i - leftLen;
- 类似"(()"或者"()(()",即这个右括号是匹配的,但是匹配后栈里面还有左括号,需要继续匹配,此时说明前面搜索到的"()"还不能和当前的"()"合并(二者中间有未匹配的左括号)。所以leftLen就是此时能得到的最大匹配长度了。
代码如下:
1 public class Solution { 2 public int longestValidParentheses(String s) { 3 if(s==null || s.length() == 0) 4 return 0; 5 6 Stack<Integer> stack = new Stack <Integer>(); 7 int totalMax = 0; 8 int currentMax = 0; 9 10 for(int i = 0;i < s.length();i++){11 if(s.charAt(i) == ‘(‘){12 stack.push(i);13 }14 else{15 //situations like ")" or "())"16 if(stack.isEmpty()){17 currentMax = 0;18 }19 else{20 int leftPos = stack.pop();21 int leftLen = i - leftPos + 1;22 23 //situations like "()" or "()()",then we can accumulate with parathesis before24 if(stack.isEmpty()){25 currentMax += leftLen;26 leftLen = currentMax;27 }28 //situations like "(()" or "(()()",there is still left parathesis, so we can‘t accumulate29 else {30 leftLen = i - stack.peek();31 }32 totalMax = Math.max(totalMax, leftLen);33 34 }35 }36 37 }38 39 return totalMax;40 }41 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。