32.最长有效括号

链接：32.最长有效括号
难度：Hard
标签：栈、字符串、动态规划
简介：给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。

题解 1 - typescript

• 编辑时间：2021-11-06
• 执行用时：84ms
• 内存消耗：40.7MB
• 编程语言：typescript
• 解法介绍：动态规划分析括号出现的状态。

function longestValidParentheses(s: string): number {
  const n = s.length;
  const dp = new Array(n + 1).fill(0);
  let ans = 0;
  for (let i = 1; i < n; i++) {
    const ch = s[i];
    if (ch === '(') dp[i + 1] = 0;
    else if (s[i - 1] === '(') dp[i + 1] = dp[i - 1] + 2;
    else if (s[i - dp[i] - 1] === '(') dp[i + 1] = dp[i] + 2 + dp[i - dp[i] - 1];
    else dp[i + 1] = 0;
    ans = Math.max(ans, dp[i + 1]);
  }
  return ans;
}