32.Longest-Valid-Parentheses

32. Longest Valid Parentheses

题目地址

https://leetcode.com/problems/longest-valid-parentheses/

https://www.cnblogs.com/grandyang/p/4424731.html

题目描述

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 "()()"

代码

Approach 1: Dynamic Programming

dp[i] 代表 s[i]

public class Solution {
    public int longestValidParentheses(String s) {
        int maxans = 0;
        int dp[] = new int[s.length()];
        for (int i = 1; i < s.length(); i++) {
              // 0. 只找右括号')'的i
            if (s.charAt(i) == ')') {
              int j = i - dp[i - 1];

              // 1. 判断i-1
              if (s.charAt(i - 1) == '(') { 
                if (i >= 2) {    //  xxxx()
                   dp[i] =  dp[i - 2] + 2;
                } else {            //  ()
                   dp[i] =  0 + 2;
                }
              } 
              // 2. 判断 j - 1 为 dp[i] 的左括号是否为‘(’
              else if (j > 0 && s.charAt(j - 1) == '(') {  
                if (j >= 2) { // xx(xxxx)
                   dp[i] = dp[j - 2] + dp[i - 1] + 2;  // dp[j - 2] 减去两个括号的位置
                } else {          // (xxxxx)
                  dp[i] = dp[i - 1] + 0 + 2; 
                }
              }

              maxans = Math.max(maxans, dp[i]);
            }
        }
        return maxans;
    }
}

Approach #2 Dyanmic Programming

dp[i] 代表 s[i]

) ( ( xxxxx ) )

dp[j - 1] j dp[i-1] / i-1 dp[i] / i

int j = i - 1 - dp[i - 1]; 是为dp[i]的左括号

class Solution {
    public int longestValidParentheses(String s) {
        int n = s.length();
        int maxLen = 0;
        int[] dp = new int[n+1];
        for (int i = 1; i < n; i++) {
            int j = i - 1 - dp[i - 1];  // dp[i]的左括号'('
            if (s.charAt(i) == '(' || j < 0 || s.charAt(j) == ')') {
                dp[i] = 0;
            } else {
                if (j > 0) {
                    dp[i] = dp[i - 1] + 2 + dp[j - 1];
                } else {
                    dp[i] = dp[i - 1] + 2;
                }
                maxLen = Math.max(maxLen, dp[i]);
            }
        }
        return maxLen;
    }
}

Approach #2 Using Stack

Time complexity && Space complexity: O(n)

class Solution {
  public int longestValidParentheses(String s) {
    int maxans = 0;
    Stack<Integer> stack = new Stack<>();
    stack.push(-1);
    for (int i = 0; i < s.length(); i++) {
      if (s.charAt(i) == '(') {
        stack.push(i);
      } else {
        stack.pop();
        if (stack.empty()) {
          stack.push(i);
        } else {
          maxans = Math.max(maxans, i - stack.peek());
        }
      }
    }

    return maxans;
  }
}

Approach #3 Without extra space

class Solution {
  public int longestValidParentheses(String s) {
    int left = 0;
    int right = 0;
    int maxlength = 0;
    for (int i = 0; i < s.length(); i++) {
      if (s.charAt(i) == '(') {
        left++;
      } else {
        right++;
      }
      if (left == right) {
        maxlength = Math.max(maxlength, 2 * right);
      } else {
        left = right = 0;
      }
    }

    left = right = 0;
    for (int i = s.length() - 1; i >= 0; i--) {
      if (s.charAt(i) == '(') {
        left++;
      } else {
        right++;
      }

      if (left == right) {
        maxlength = Math.max(maxlength, 2 * left);
      } else if (left > right) {
        left = right = 0;
      }
    }

    return maxlength;
  }
}