首页 > 代码库 > 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.
Analysis: 这道题真是让我想了很久，之前做过的有关Parentheses的题目都没有遇到这种难度的。真是体会到好的算法抵过千万行代码啊。我尝试了几种方法：
1. Naive Solution: 遍历String的所有substring, 选取最长的matched substring, 不用说，这种做法的复杂度为O(N^3)，绝对是不可能通过OJ的大case测试的，一定会TLE
2. 把String中所有的‘(’ 作为 start, 因为我们知道matched string一定是以 ‘(’ 开始的。由这个 start开始寻找最长的matched string，这样做的时间复杂度为O(N^2), 我依然知道不是最优的，肯定有O(N)的算法
3. DP方法，这个想法并不成熟，就是从寻找一个最基本的配对单元 ‘()‘开始，逐步递推。isValid[i][j]表示从i到j是否是一个valid的表达式。isValid[i][j]为真的条件可以递推。这个想法太过艰深，没有深入
4. 想到了用Stack的方法，结果因为其中一个细节想不出来该怎么处理而放弃了。这个细节是：比如S是（）（（））），最长的matched substring是 （）（（））, 可是用stack能检查到（），能检查到（（）），但是如何检查到它们一起？我当时不知道怎么办了。后来查看了网上的解答，发现别人也用Stack，做法令人叹为观止，很好地解决了我的这个问题。下面会讲：
于是我贴上参考了网上别人解答以后我用stack的解法吧：
Solution Analysis: 遍历S。遇到‘(‘，放入lefts。如果遇到‘)‘，如果lefts是空，说明这是一个无法匹配的‘)‘，记录下last。last里面存放的其实是最后一个无法匹配的‘)‘。为啥要保存这个值呢？主要是为了计算后面完整的表达式的长度。可以这样理解： “所有无法匹配的‘)‘”的index其实都是各个group的分界点。这样做非常好地解决了我之前说的那个如何检验（）（（））的问题。如果lefts不是空，说明栈内还有‘(‘, 一个最外层完整的group还没有匹配完成，但是怕后面S没有更多元素了，所以需要计算当前已经完整部分表达式的长度，有可能把它用作maxlen。
1 public class Solution { 2 public int longestValidParentheses(String s) { 3 int Maxlen = 0; 4 int lastleft = -1; 5 Stack<Integer> lefts = new Stack<Integer>(); 6 for (int i = 0; i < s.length(); i++) { 7 if (s.charAt(i) == ‘(‘) { //new element is ‘(‘ 8 lefts.push(i); 9 }10 else { //new element is ‘)‘11 if (lefts.empty()) { // ‘)‘ is not matched, denote this index, as a dividing node12 lastleft = i;13 }14 else { // ‘)‘ is matched15 lefts.pop();16 if (lefts.empty()) { // no more ‘(‘ left in Stack lefts17 Maxlen = Math.max(Maxlen, i - lastleft);18 }19 else {20 Maxlen = Math.max(Maxlen, i - lefts.peek());21 }22 }23 }24 }25 return Maxlen;26 }27 }