32. 最长有效括号

leetcode python 字符串动态规划困难

LeetCode

发布日期: 2020-10-14

更新日期: 2020-10-21

文章字数: 922

阅读时长: 3 分

阅读次数:

一、题目

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

示例 1:

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

示例 2:

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

二、思路

1. 栈

创建一个空栈stack，同时创建一个标志数组flag，数组长度等于字符串s长度，初始值全部为0（0代表非有效括号，1代表有效括号一部分）。

对字符串s进行遍历，当遍历到的字符是(，则将其下标添加到栈stack中。如果是)，并且栈不为空，则将栈顶下标抛出，同时将栈顶下标与当前遍历的下标在flag中的对应位置的值改为1。

当字符串s遍历结束，然后对标志数组flag进行遍历。统计数组中连续为1的长度，然后与max_length（有效括号最大长度）对比，将比较大的值赋值给max_length。

最后返回max_length。

2. 动态规划

我们首先定义一个数组dp，用来统计最长有效括号的长度，数组长度与字符串s的长度相等，并且将值全部初始化为0。用dp[i]表示以下标为i的元素为结尾的最长有效括号的长度。

我们还知道有效括号必须以)结尾，所以我们只需要计算)在dp数组中对应位置上的值即可。

我们从前往后遍历字符串s，遇到)边进行统计，由于要形成有效括号，字符串s长度至少为2，所以代码中直接从第二个元素也就是下标为1的位置开始遍历：

如果s[i] == ")"：

情况一：如果s[i-1] == "("，这时s[i]与s[i-1]正好是一对有效括号，所以
$$
dp[i] == dp[i-2] + 2
$$
如果s[i-1] == ")"，这时我们就需要判断s[i - dp[i-1] - 1] == "("，如果成立，那么
$$
dp[i] = dp[i-1] + dp[i - dp[i-1] - 2] + 2
$$

到此为止，已经得到状态转移方程，接下来需要进行一些条件限定：

在第一种情况中，需要确保i-2 >= 0
在第二种情况中，要保证i - dp[i-1] - 1 >= 0

最后返回数组dp中的最大值。

三、代码

1. 栈

class Solution:
    def longestValidParentheses(self, s: str) -> int:
        # 栈
        stack = []
        # 标志数组，保存有效括号的位置
        flag = [0 for _ in range(len(s))]
        # 有效括号的最大长度
        max_length = 0
        # 当前有效括号的长度
        cur = 0
        for i in range(len(s)):
            if s[i] == '(':
                stack.append(i)
            elif s[i] == ')' and stack:
                index = stack.pop()
                flag[i], flag[index] = 1, 1

        for k in range(len(flag)):
            if flag[k]:
                cur += 1
                # 保证当前元素不是最后一个
                if k + 1 < len(flag):
                    # 下一个标志位置为0，则进行长度比较、更新
                    if not flag[k+1]:
                        max_length = max(cur, max_length)
                else:
                    max_length = max(cur, max_length)
            else:
                cur = 0
        return max_length

2. 动态规划

class Solution:
    def longestValidParentheses(self, s: str) -> int:
        n = len(s)
        # 创建一个dp数组
        dp = [0 for _ in range(n)]

        for i in range(1, n):
            if s[i] == ')':
                if s[i-1] == '(':
                    dp[i] = (dp[i-2] if i-2>=0 else 0) + 2
                elif s[i-1] == ')':
                    if i-dp[i-1]-1>=0 and s[i - dp[i-1] - 1] == '(':
                        dp[i] = dp[i-1] + dp[i- dp[i-1] -2] + 2

        return max(dp if dp else [0])