首页 > 代码库 > 【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 }