Longest Valid Parentheses 32(LeetCode)

Question

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.

Solution

这道题求最值，首先想到的是DP。

DP[i]表示以S[i]结尾的（即必须包括S[i]）的longest valid parentheses。

状态函数：

1. 如果S[i] == '('，则以S[i]结尾的序列必然不可能是合法的，因此DP[i]=0。

2. 如果S[i] == ')'，则如果DP[i - 1]的最长序列前一位（假设为j）存在且为'('，j=i - 1 - DP[i - 1]，则S[i]可以和S[j]匹配，其长度为DP[i-1]+2（即以i-1位结尾的最长字串加上S[j]和S[i]），同时和以j-1位结尾的最长字串连起来组成新的最长字串。注意j和j-1位不一定存在。如果第j位不存在或者无法和S[i]匹配(S[j]==')')，则DP[i]=0。

这里可以证明，不存在j' < j，且s[j' : i]为valid parentheses substring。

证明：

假如存在这样的j'，如果则s[j' : i]为valid parentheses substring，则s[j'+1 : i-1]也一定为valid（前后字符匹配，剩下的中间字符必须全部valid才能使得整体都是valid），这和i-1位的最长字串只到j+1不符合。

第二种方法受到valid parentheses的启发，可以用stack来解，只不过栈中保存的是index。

1. 遇到'('无条件入栈

2. 遇到')'则需要和栈中保存的'('配对消除，这时候又分两种情况：

1） 栈空。则之前的valid串到此为止，需要将此时的位置记录为新的开始位置，即用一个start来记录此时的index。

2）栈不空。如果栈中'('出栈之后栈依然不空，则将栈顶元素的index作为边界，用此时的index减去栈顶元素的index即可求出新长度。如果出栈后栈变为空，则将start记录的位置作为边界，用此时的index减去start即可求出新长度。将新长度与最大长度比较，如果更大则更新最大长度。

代码如下：

public class Solution {
    public int longestValidParentheses(String s) {
        if(s == null || s.length() <= 1){
            return 0;
        }

        //stack version
        // Stack<Integer> stack = new Stack<Integer>();
        // int start = -1;
        // int maxLength = 0;
        // for(int i = 0; i < s.length(); i++){
        //     if(s.charAt(i) == '('){
        //         stack.push(i);
        //     }

        //     if(s.charAt(i) == ')'){
        //         if(!stack.isEmpty()){
        //             stack.pop();
        //             if(!stack.isEmpty()){
        //                 maxLength = Math.max(maxLength, i - stack.peek());
        //             }else{
        //                 maxLength = Math.max(maxLength, i - start);
        //             }
        //         }else{
        //             start = i;
        //         }
        //     }
        // }

        // return maxLength;

        //DP version
        char[] S = s.toCharArray();
        int[] DP = new int[S.length];
        int max = 0;
        for(int i = 1; i < S.length; i++){
            if(S[i] == ')'){
                int j = i - 1 - DP[i - 1];
                if(j >= 0 && S[j] == '('){
                    DP[i] = 2 + DP[i - 1] + (j > 0? DP[j - 1] : 0);
                }
            }

            max = Math.max(max, DP[i]);
        }

        return max;
    }
}