括号有效配对一箭三连（三） | 刷题打卡

一、题目描述：

1） 任何一个左括号都能找到和其正确配对的右括号
2） 任何一个右括号都能找到和其正确配对的左括号
返回一个括号字符串中，最长的括号有效子串长度

示例：

示例 1：

输入：(()))
输出：4

示例 2：

输入：()(()))
输出：6

示例 3：

输入：)()())
输出：4

二、思路分析：

当问到最长有多少时，可以考虑使用动态规划去实现。定义一个辅助数组dp，用于记录字符串当前字符最大有效括号长度。

遍历字符串

1、当遇到'('时，最长有效字符串长度为0；

2、当遇到')'时，就需要看前面一个dp的值
如果i-1最长有效长度为0

• i-2前面没有字符，那么i位置的有效长度就为2；
• i-2前面还有字符，有效长度就为2 + dp[i-dp[i-1]-1]。

如果i-1最长有效长度为不为0

• 就要追溯到i-1位置最长有效长度的前一位，判断该位是不是可以和当前匹配，如果可以就需要加上dp[i-dp[i-1]-1]，即2+ dp[i-dp[i-1]-1] + dp[i-1]。(例：s='(()())', s[5]可以和s[0]匹配，有效长度为2 + 0 + 4 = 6)

总之，抽象起来就是：看第i-1个有效字符串长度是否等于'(',等于就需要看第i-1个有效字符串长度的前一位，前一位存在就需要加上，不存在就不需要加。 例： s='()()))'

例： s=')(()())'

三、AC 代码：

function maxLength(s) {
  if (s == null || s.length < 2) return 0
  let dp = new Array(s.length).fill(0)
  let max = 0
  for (let i = 0; i < s.length; i++) {
    if (s[i] === ')') {
      let pre = i - dp[i - 1] - 1
      if (s[pre] === '(' && pre >= 0) {
        dp[i] = dp[i - 1] + 2 + (pre > 0 ? dp[pre - 1] : 0)
      }
    }
    max = Math.max(max, dp[i])
  }
  console.log(dp)
  return max
}

四、总结：

遇到最值问题，将问题抽象成以什么什么开头或结尾，求其i-1位置的值。再考虑包的含情况及关系等式。