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。

public class Solution {
    public int longestValidParentheses(String s) {
        int Maxlen = 0;
        int lastleft = 0;
        Stack<Integer> lefts = new Stack<Integer>();
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(') { //new element is '('
                lefts.push(i);
            }
            else { //new element is ')'
                if (lefts.empty()) { // ')' is not matched, denote this index, as a dividing node
                    lastleft = i + 1;
                }
                else { // ')' is matched
                    lefts.pop();
                    if (lefts.empty()) { // no more '(' left in Stack lefts
                        Maxlen = Math.max(Maxlen, i - lastleft + 1);
                    }
                    else {
                        Maxlen = Math.max(Maxlen, i - lefts.peek());
                    }
                }
            }
        }
        return Maxlen;
    }
}