leetcode32.Longest Valid Parentheses

题目要求

原题地址：https://leetcode.com/problems/longest-valid-parentheses/#/description

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.

一个括号序列，求出其中成对括号的最大长度

思路一：使用堆栈

这题可以参考我的另一篇博客,这篇博客讲解了如何用堆栈判断括号序列是否可以成对。我们可以将堆栈的思路延续到这里。每当遇到一个左括号或者是无法成对的右括号，就将它压入栈中，可以成对的括号则从栈中压出。这样栈中剩下的就是无法成对的括号的下标。这时我们可以判断这些下标间的距离来获得最大的成对括号长度。在这里需要先遍历一遍字符串，再遍历一下非空的堆栈。

public int longestValidParentheses(String s) {
    Stack<Parenthese> parenthesesStack = new Stack<Parenthese>();
    for(int i = 0 ; i < s.length() ; i++){
        char symbol = s.charAt(i);
        if(symbol==')'){
            //在这里左右括号可以成对，则出栈
            if(!parenthesesStack.isEmpty() && parenthesesStack.peek().symbol=='('){
                parenthesesStack.pop();
                continue;
            }
        }
        //其他情况都压入栈中
        parenthesesStack.push(new Parenthese(symbol, i));
    }
    int maxLength = 0;
    int nextIndex = s.length();
    while(!parenthesesStack.isEmpty()){
        int curIndex = parenthesesStack.pop().index;
        maxLength = (nextIndex-curIndex-1)>maxLength ? nextIndex-curIndex-1 : maxLength;
        nextIndex = curIndex;
    }
    return Math.max(nextIndex, maxLength);
}

public class Parenthese{
    char symbol;
    int index;
    public Parenthese(char symbol, int index){
        this.symbol = symbol;
        this.index = index;
    }    
}

在这里可以优化，因为使用数据结构不是必要的。我们可以直接压入栈中下标，再从字符串中获得该下标对应的字符

public int longestValidParentheses_noDataStructure(String s) {
    Stack<Integer> parenthesesStack = new Stack<Integer>();
    for(int i = 0 ; i < s.length() ; i++){
        if(s.charAt(i)==')'){
            if(!parenthesesStack.isEmpty() && s.charAt(parenthesesStack.peek())=='('){
                parenthesesStack.pop();
                continue;
            }
        }
        parenthesesStack.push(i);
    }
    int maxLength = 0;
    int nextIndex = s.length();
    while(!parenthesesStack.isEmpty()){
        int curIndex = parenthesesStack.pop();
        int curLength = nextIndex-curIndex-1;
        maxLength = curLength>maxLength ? curLength : maxLength;
        nextIndex = curIndex;
    }
    return Math.max(nextIndex, maxLength);
}

思路二：dynamic programming

dynamic programming 的真 奥义其实在于假设已知之前所有的结果，结合之前的结果穷尽每一种当前值可能的情况
在这道题目中，我们假设已经知道长度为n-1字符串中，到每一个下标为止的的最大的括号组长度，这些值被存储在和字符串长度等长的int数组s中，其中s的下标代表字符串的下标，s的值代表到这个字符串下标为止最长括号组长度。
那么当前第n个符号主要有以下三种情况:

1. 当前值为‘(’，那么无论前面情况如何，当前一定是无法形成括号的，所以最大长度为0
2. 当前值为‘)’，前一个值为‘(‘, 那么最大长度为s[n-2](如果存在的话）+ 2
3. 当前值为‘)’，前一个值也是’)’，如果在i-s[i-1]-1的位置上是一个’(‘，那么最大长度为s[i-1]+2+s[i-s[i-1]-2]，具体情况可以参考()(())当n=5时,否则仍旧为0

代码实现如下

public int longestValidParentheses_dynamicProgramming(String s) {
    int[] maxCount = new int[s.length()];
    int maxLength = 0;
    for(int i = 1 ; i<s.length() ; i++){
        if(s.charAt(i) == ')'){
            if(s.charAt(i-1)=='('){
                maxCount[i] = (i>=2? maxCount[i-2]+2 : 2);
                maxLength = Math.max(maxCount[i], maxLength);
            }else{
                if(i-maxCount[i-1]-1>=0 && s.charAt(i-maxCount[i-1]-1)=='('){
                    maxCount[i] = maxCount[i-1]+2 + ((i-maxCount[i-1]-2 >= 0)?maxCount[i-maxCount[i-1]-2]:0);;
                    maxLength = Math.max(maxCount[i], maxLength);
                }
            }
        }
    }
    return maxLength;        
}

简化后的代码如下：

public int longestValidParentheses_dynamicProgrammingConcise(String s) {
    int[] maxCount = new int[s.length()];
    int maxLength = 0;
    for(int i = 1 ; i<s.length() ; i++){
        if(s.charAt(i) == ')' && i-maxCount[i-1]-1>=0 && s.charAt(i-maxCount[i-1]-1)=='('){
            maxCount[i] = maxCount[i-1] + 2 + ((i-maxCount[i-1]-2>=0) ? maxCount[i-maxCount[i-1]-2] : 0);
            maxLength = Math.max(maxCount[i], maxLength);
            
        }
    }
    return maxLength;        
}