32. 最长有效括号

[Geekhyt]

原题链接

子问题

dp[i]: 表示以 s[i] 结尾的最长有效括号长度。

状态转移方程

分情况讨论出所有可能：

s[i] 可能为 '(' 或者 ')'：

1. s[i] === '(' 时，不可能组成有效的括号，所以 dp[i] = 0。
2. s[i] === ')' 时，需要查看 s[i - 1]。
   • s[i - 1] === '(' 时，s[i - 1] 和 s[i] 可以组成一对有效括号，需要查看 s[i - 2]。
     • s[i - 2] 不存在，则有效长度为 2。 dp[i] = 2
     • s[i - 2] 存在，则需要在 2 的基础上加上以 s[i - 2] 为结尾的最长有效长度。dp[i] = dp[i - 2] + 2
   • s[i - 1] === ')' 时，此时 s[i - 1] 和 s[i] 合起来是 '))'，需要查看 s[i - dp[i - 1] - 1]。
     • s[i - dp[i - 1] - 1] 不存在或为 ')'，则 s[i] 找不到匹配，所以 dp[i] = 0。
     • s[i - dp[i - 1] - 1] 是 '('，与 s[i] 匹配。此时需要查看 s[i - dp[i - 1] - 2]是否存在。
       • s[i - dp[i - 1] - 2] 不存在，dp[i] = dp[i - 1] + 2
       • s[i - dp[i - 1] - 2] 存在，dp[i] = dp[i - 1] + dp[i - dp[i - 1] - 2] + 2

用代码表示出来即可：

const longestValidParentheses = function(s) {
  let res = 0
  const len = s.length
  const dp = new Array(len).fill(0)
  for (let i = 1; i < len; i++) {
    if (s[i] == ')') {
      if (s[i - 1] == '(') {
        if (i - 2 >= 0) {
          dp[i] = dp[i - 2] + 2
        } else {
          dp[i] = 2
        }
      } else if (s[i - dp[i - 1] - 1] == '(') {
        if (i - dp[i - 1] - 2 >= 0) {
          dp[i] = dp[i - 1] + 2 + dp[i - dp[i - 1] - 2]
        } else {
          dp[i] = dp[i - 1] + 2
        }
      }
    }
    res = Math.max(res, dp[i])
  }
  return res
}

• 时间复杂度：O(n)
• 空间复杂度：O(n)