32. Longest Valid Parentheses

1. 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.

2. Difficulty:

Hard(not that hard)

3 .Some Tricky Test Case:

1
2
3

()()))))()()(
()(())
(()()))

4. Relative Problems:

1 2	20. Valid Parentheses (easy) 22. Generate Parentheses(Medium)Solutions:

5. Solution:

Input: String s, return int longest.

(1). use stack：

The main Idea is that we should put all the elements into stack, check whether there is a Valid Parenthese.

if we get s.charAt(i) == ‘(‘ , we should put the index into stack.

if we get s.charAt(i) == ‘)’, we should check top of stack,

if the top of the stack is (, pop it out. Everthing goes well, we get a Valid Parentheses.

But if the top of the stack is ), we should push the index into stack.

e.g. : )()()).
      Stack(bottom to top): {0,5}
e.g. : ()()))))()()(.
true  Stack(bottom to top): {4,5,6,7,12}.
true  longest is 4. (12 - 1) - 7.
true   			4. (4 - 1) - ?. So I set when the stack is empty. ? = -1.

As we can see, we get all invalid elements index.

If the stack is empty, just need to return s.length.

If the stack is not empty, we need to get longest Valid Parenthese.

6. Code:

public static int longestValidParentheses(String s) {
        Stack<Integer> chars = new Stack<>();
        int longest = 0;
        int pre = s.length();
        //push stack
        for(int i = 0; i < s.length();i++){
            //check whether stack is empty.
            if(chars.empty()||s.charAt(i) == '(')chars.push(i);//empty or ( push
            else if(s.charAt(chars.peek()) == '(')// ) if top is ( pop out
                chars.pop();
            else chars.push(i);//if top is )
        }
        if(chars.empty()) return s.length();
        int temp = 0;//just a flag
        while (temp != -1) {
            //若此时栈空了，那么说明此时的temp就是余下的( or ) return 他的位置，但逻辑就不统一了。
            //或者pop完 栈空，那么 他的位置就是长度。
            //else 他的位置长度 - 1 - 上一位。
            temp = chars.empty() ? -1 : chars.pop();//empty temp = -1
            longest = longest > (pre - 1) - temp ? longest : (pre - 1) - temp;
            pre = temp;//previous stack.
        }

        return longest;
    }

(2). Dynamic Programming:

(()()))如果是（，len[i] = 0;如果是），如果上一个是（，则 len[i]=2 （1）如果上一个是），则要看i - len[i] - 1位的情况 (()())即此时最右边，你得看第5 - 4 - 1 = 0位的情况，（2）如果是（，那么len[i] = len[i - 1] + 2;但如果是这种情况()(())，同时我们得看上上一位，即我们新加一个），i - len[i - 1] -2处也可以算入最长序列了。()()或者是这样，说明在（1),（2）两种情况时，都可以获得增长，因此我们最后都要加上len[i - len[i - 1] -2]。

main idea: use array len to store length

if s[i] = ‘(‘, len = 0;

if s[i] = ‘)’, len = the length of near Valid Parentheses.

Analysis:

if, left is ‘(‘, len at least = 2 , we still need to check s[i - 2]. just add len[i - 2].

if, left is ‘)’, we need to check i - len[i - 1] -1, jump to last invalid place to check whether we could get more. if s[i - len[i - 1] - 1] = (; we could get more!

now len[i] = len[i - 1] + 2 + len[i - len[i - 1] - 2]

check len[i - len[i - 1] - 2] to see whether we can get more!

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

那么我们可以观察得到条件可以合并，i-1 == (不再重要，反正大家都要加2，而且i-1 == （，len【i-1】==0加不加无所谓

Try to observe the if condition, we can get a more concise version!

if(s.charAt(i) == ')'&&i - len[i - 1] - 1 >= 0&& s.charAt(i - len[i - 1] - 1) == '(')
{
  len[i] = len[i - 1] + 2 + (i - len[i - 1] -2 >= 0? len[i - len[i - 1] -2]:0);
  max = Math.max(len[i],max);
}//对于这段程序的理解：如果加入的是)，那么要开始改变的。
// 我们要找上上个（，在且只可能在i - len[i - 1] - 1，如果是个（，那么长度可以+2
// 同时看看能不能变的更长。要看上上一个（左边的序列。

你好

LeetCode32