32. Longest Valid Parentheses

Question:

Given a string containing just the characters ‘(‘ and ‘)’, find the length of the longest valid (well-formed) parentheses substring.

Example 1:

Input: "(()"
Output: 2
Explanation: The longest valid parentheses substring is "()"

Example 2:

Input: ")()())"
Output: 4
Explanation: The longest valid parentheses substring is "()()"

Thinking:

• Method1:通过栈
  1. 从头向尾遍历整个字符串，如果是左括号则将index入栈，如果是右括号则判断栈顶是不是左，如果是则出栈（说明合法），如果不是则将右括号的index入栈。
  2. 遍历结束后，栈内的所有index都为不合法，同时说明其中的子串是合法的，我们求出最长的距离。

class Solution {
    public int longestValidParentheses(String s) {
        if(s == null) return 0;
        int len = s.length();
        if(len == 0 || len == 1) return 0;
        Stack<Integer> stack = new Stack<>();
        for(int i = 0; i < len; i++){
            char c = s.charAt(i);
            if(c == '(')
                stack.push(i);
            else{
                if(!stack.empty()){
                    if(s.charAt(stack.peek()) == '(')
                        stack.pop();
                    else
                        stack.push(i);
                }else
                    stack.push(i);
            }
        }
        if(stack.empty()){
            return len;
        }
        int up = len;
        int current = 0;
        int max = 0;
        while(!stack.empty()){
            current = stack.pop();
            max = Math.max(max, up - current - 1);
            up = current;
        }
        max = Math.max(max, current);
        return max;
    }
}

• Method 2:DP
  • 在’(‘处不需要更新
  • 在‘）’分两种情况
    • 前一个是‘（’，直接将前前一个的值+2.
    • 前一个是’)’, 则要查看上一个对应的’(‘的前一个是不是’(‘，再加上之前的值。

class Solution {
    public int longestValidParentheses(String s) {
        if(s == null || s.length() == 0) return 0;
        int len = s.length();
        int result = 0;
        int[] dp = new int[len + 1];
        char[] arr = s.toCharArray();
        for(int i = 1; i < arr.length; i++){
            char c = arr[i];
            if(c == ')'){
                if(arr[i - 1] == '('){
                    dp[i + 1] = dp[i - 1] + 2;
                    result = Math.max(result, dp[i + 1]);
                }
                else if(arr[i - 1] == ')'){
                    if(i - 1 - dp[i] >=0 && arr[i - 1 - dp[i]] == '('){
                        dp[i + 1] = dp[i] + 2 + ((i - 1 - dp[i] >= 0) ? dp[i - 1 - dp[i]] : 0);
                        result = Math.max(result, dp[i + 1]);
                    }
                }
            }
        }
        return result;
    }
}

二刷

1. 首先回忆起来的是通过栈来做的方法。

class Solution {
    public int longestValidParentheses(String s) {
        if(s == null || s.length() == 0) return 0;
        Stack<Character> st1 = new Stack<>();
        Stack<Integer> st2 = new Stack<>();
        for(int i = 0; i < s.length(); i++){
            char c = s.charAt(i);
            if(c == '('){
                st1.push(c);
                st2.push(i);
            }else{
                if(!st1.isEmpty() && st1.peek() == '('){
                    st1.pop();
                    st2.pop();
                }else{
                    st1.push(c);
                    st2.push(i);
                }
            }
        }
        int max = 0, val = s.length() - 1, temp = 0;
        if(st2.isEmpty()) return s.length();
        max = val - st2.peek();
        while(!st2.isEmpty()){
            temp = st2.pop();
            max = val - temp - 1 > max ? val - temp - 1 : max;
            val = temp;
        }
        return Math.max(max, val);
    }
}

2.使用DP的方法

class Solution {
    public int longestValidParentheses(String s) {
        if(s == null || s.length() == 0) return 0;
        int len = s.length();
        int[] dp = new int[len + 1];
        int result = 0;
        for(int i = 1; i <= len; i++){
            char c = s.charAt(i - 1);
            if(c == ')'){
                if(i > 1 && s.charAt(i - 2) == '('){
                    dp[i] = dp[i - 2] + 2;
                    result = Math.max(result, dp[i]);
                }else if(i > 1 && s.charAt(i - 2) == ')'){
                    if(dp[i - 1] != 0){
                        if(i - 2 - dp[i - 1] >= 0 && s.charAt(i - 2 - dp[i - 1]) == '('){
                            dp[i] = dp[i - 1] + 2;
                            if(i - 2 - dp[i - 1] >= 0 && dp[i - 2 - dp[i - 1]] > 0){
                                dp[i] += dp[i - 2 - dp[i - 1]];
                            }
                            result = Math.max(result, dp[i]);
                        }
                    }
                }
            }
        }
        return result;
    }
}