[32][困难][动态规划][栈] 最长有效括号

题目描述

32. 最长有效括号

给定一个只包含 '(' 和 ')' 的字符串，找出最长的包含有效括号的子串的长度。

示例 1:

输入: "(()"
输出: 2
解释: 最长有效括号子串为 "()"

示例 2:

输入: ")()())"
输出: 4
解释: 最长有效括号子串为 "()()"

解题思路

栈

思路参考: 最长有效括号

可以观察到, 导致只包含左右圆括号字符串整体不有效的原因有两种情况:

• 左侧左圆括号(过多, 右侧的右圆括号)只覆盖了一部分

• 左侧右圆括号)过多

对于第一种情况, 只要后面又出现右圆括号), 就可以修复, 从而整体括号都有效. 但第二种情况, 一旦出现右圆括号)过多, 这个位置之前的部分就无法修复了. 而且判断右圆括号过多只需使用到当前字符为止的子串, 不需要后续信息.

使用栈结构来解题, 结合上面的特点, 我们希望:

• 遇到左圆括号(, 则将左圆括号的信息压入栈中

• 遇到右圆括号)

  • 如果能够找到相匹配的左圆括号(, 能够将这个左圆括号(的信息消去, 而且能够求得匹配的长度

  • 如果不能够匹配, 说明是后续子串左侧的过多字符, 应当留在栈中

另外可以发现, 最长有效括号的长度, 一定等于这个有效序列最后一个字符的下标, 减去前面最后一个没有被匹配的字符的下标, 如果有效序列从下标0开始, 认为最后一个没有匹配的下标为-1.

最后栈的解法如下:

• 首先在栈中压入一个-1表示最后一个没有被匹配的括号的下标

• 对于遇到的每个左圆括号(, 将它的下标放入栈中

• 对于遇到的每个右圆括号), 首先弹出栈顶元素, 假设当前右括号能够匹配

  • 如果栈不为空, 认为匹配成功, 当前右括号的下标减去栈顶元素即为以该右括号为结尾的最长有效括号的长度. 因为栈顶元素已经弹出来, 此时在栈顶的不是所匹配的左括号下标

  • 如果栈为空, 说明当前的右括号没有找到匹配, 我们将其下标放入栈中来更新最后一个没有被匹配的右括号的下标

为什么栈的空与否能作为判断匹配成功的标志?

• 栈中首先压入了一个-1, 一开始就不是空的

• 如果能够匹配, 则对应的左括号下标已经被压入其中, 弹出的是该左括号的下标, 栈中一定还有最后一个没有被匹配的右括号的下标

• 在遇到右括号时, 首先将栈顶元素弹出, 当不匹配时, 再将该右括号的下标压入栈中, 代替原来下标, 成为新的最后一个没有被匹配的右括号的下标. 因此栈中有且只有一个最后一个没有被匹配的右括号的下标, 这也与我们的判断逻辑相符, 我们不再需要之前的信息, 滚动更新边界即可.

  • 而在遇到右括号时, 首先将栈顶元素弹出, 此时的栈就为空了

• 如果累计了大量的左括号, 栈中会有很多下标, 这时来一个有括号肯定是匹配的, 而此时的栈也不为空, 满足栈不空则匹配的逻辑

最后代码如下:

class Solution:
    def longestValidParentheses(self, s: str) -> int:
        stack = [-1]
        max_len = 0

        for i, c in enumerate(s):
            if c == '(':
                stack.append(i)
            else:
                stack.pop()
                if stack:
                    max_len = max(max_len, i - stack[-1])
                else:
                    stack.append(i)
        return max_len

动态规划

思路参考: 最长有效括号

首先定义状态$dp[i]$表示以下标$i$字符结尾的最长有效括号的长度, 初始化时所有位置为0即可.

状态转移考虑如下:

• 下标$i$对应的字符若为左圆括号(, 肯定不是有效子串的结尾, $dp[i]$保持为0

• 下标$i$对应的字符若为右圆括号)

  • 可能与左边紧邻的字符匹配, 若匹配, 长度在$dp[i - 2]$的基础上加2, 即

    若$s[i]=\text{`)`}$, 且$s[i-1]=\text{`(`}$时, 状态转移方程为$dp[i]=dp[i - 2]+2$

  • 可能与左边非紧邻字符匹配, 将$dp[i - 1]$指示的子串包裹起来, 此时有:

    $s[i]=\text{`)`}$且$s[i-1]=\text{`)`}$, 且$s[i-dp[i-1]-1]=\text{`(`}$, 状态转移方程为$dp[i]=dp[i - 1]+2+dp[i-dp[i-1]-2]$

总之, 注意匹配子串的串联关系.

class Solution:
    def longestValidParentheses(self, s: str) -> int:
        cache = [0] * len(s)
        max_len = 0
        for i, c in enumerate(s):
            if c == ')':
                if i - 1 >= 0:
                    if s[i - 1] == '(':
                        cache[i] = (cache[i - 2] if i - 2 >= 0 else 0) + 2
                    else:  # s[i - 1]为)
                        if i - cache[i - 1] - 1 >= 0 and s[i - cache[i - 1] - 1] == '(':
                            cache[i] = cache[i - 1] + 2 + (cache[i - cache[i - 1] - 2] if i - cache[i - 1] - 2 >= 0 else 0)
                max_len = max(max_len, cache[i])
        return max_len