No.32 最长有效括号

给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号 子串 的长度。

示例 1：

输入：s = "(()"
输出：2
解释：最长有效括号子串是 "()"

示例 2：

输入：s = ")()())"
输出：4
解释：最长有效括号子串是 "()()"

示例 3：

输入：s = ""
输出：0

提示：

• 0 <= s.length <= 3 * 10^4
• s[i] 为 '(' 或 ')'

解题思路

实现

动态规划

dp[i]: 以下标为 i 字符结尾的最长有效括号长度; dp[0...max]=0 有效子串一定以 ) 结尾，以 ( 结尾的子串的 dp = 0，因此只需求解 ) 在 dp 数组中对应位置的值

1. s[i]=) && s[i-1]=( => dp[i]=dp[i-2]+2
2. s[i]=) && s[i-1]=) => s[i-dp[i-1]-1]=( => dp[i]=dp[i-1]+dp[i-dp[i-1]-2]+2

/**
 * @param {string} s
 * @return {number}
 */
var longestValidParentheses = function (s) {
  let maxLength = 0;
  let dp = new Array(s.length).fill(0);
  for (let i = 0; i < s.length; i++) {
    if (s[i] === ")") {
      if (s[i - 1] === "(") {
        dp[i] = (i >= 2 ? dp[i - 2] : 0) + 2;
      } else if (
        s[i - 1] === ")" &&
        i > dp[i - 1] &&
        s[i - 1 - dp[i - 1]] === "("
      ) {
        dp[i] =
          (i - dp[i - 1] >= 2 ? dp[i - dp[i - 1] - 2] : 0) + dp[i - 1] + 2;
      }
    }
    maxLength = Math.max(maxLength, dp[i]);
  }
  return maxLength;
};

栈

/**
 * @param {string} s
 * @return {number}
 */
var longestValidParentheses = function (s) {};

字符串

/**
 * @param {string} s
 * @return {number}
 */
var longestValidParentheses = function (s) {};