括号有效配对一箭三连（三）

一、题目描述：

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位置的值。再考虑包的含情况及关系等式。

作者：ClyingDeng

链接：https://juejin.cn/post/6951262583894573087

来源：稀土掘金

著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。