0032. 最长有效括号

0032. 最长有效括号 #

  • 标签:栈、字符串、动态规划
  • 难度:困难

题目大意 #

描述:给定一个只包含 '('')' 的字符串。

要求:找出最长有效(格式正确且连续)括号子串的长度。

说明

  • $0 \le s.length \le 3 * 10^4$。
  • s[i]'('')'

示例

  • 示例 1:
1
2
3
输入s = "(()"
输出2
解释最长有效括号子串是 "()"
  • 示例 2:
1
2
3
输入s = ")()())"
输出4
解释最长有效括号子串是 "()()"

解题思路 #

思路 1:动态规划 #

1. 划分阶段 #

按照最长有效括号子串的结束位置进行阶段划分。

2. 定义状态 #

定义状态 dp[i] 表示为:以字符 s[i] 为结尾的最长有效括号的长度。

3. 状态转移方程 #
  • 如果 s[i] == '(',此时以 s[i] 结尾的子串不可能构成有效括号对,则 dp[i] = 0
  • 如果 s[i] == ')',我们需要考虑 s[i - 1] 来判断是否能够构成有效括号对。
    • 如果 s[i - 1] == '(',字符串形如 ......(),此时 s[i - 1]s[i](),则:
      • dp[i] 取决于「以字符 s[i - 2] 为结尾的最长有效括号长度」 + 「s[i - 1]s[i] 构成的有效括号对长度(2)」,即 dp[i] = dp[i - 2] + 2
      • 特别地,如果 s[i - 2] 不存在,即 i - 2 < 0,则 dp[i] 直接取决于 「s[i - 1]s[i] 构成的有效括号对长度(2)」,即 dp[i] = 2
    • 如果 s[i - 1] == ')',字符串形如 ......)),此时 s[i - 1]s[i]))。那么以 s[i - 1] 为结尾的最长有效长度为 dp[i - 1],则我们需要看 i - 1 - dp[i - 1] 位置上的字符 s[i - 1 - dp[i - 1]]是否与 s[i] 匹配。
      • 如果 s[i - 1 - dp[i - 1]] == '(',则说明 s[i - 1 - dp[i - 1]]s[i] 相匹配,此时我们需要看以 s[i - 1 - dp[i - 1]] 的前一个字符 s[i - 1 - dp[i - 2]] 为结尾的最长括号长度是多少,将其加上 ``s[i - 1 - dp[i - 1]]s[i]`,从而构成更长的有效括号对:
        • dp[i] 取决于「以字符 s[i - 1] 为结尾的最长括号长度」 + 「以字符 s[i - 1 - dp[i - 2]] 为结尾的最长括号长度」+ 「s[i - 1 - dp[i - 1]]s[i] 的长度(2)」,即 dp[i] = dp[i - 1] + dp[i - dp[i - 1] - 2] + 2
        • 特别地,如果 s[i - dp[i - 1] - 2] 不存在,即 i - dp[i - 1] - 2 < 0,则 dp[i] 直接取决于「以字符 s[i - 1] 为结尾的最长括号长度」+「s[i - 1 - dp[i - 1]]s[i] 的长度(2)」,即 dp[i] = dp[i - 1] + 2
4. 初始条件 #
  • 默认所有以字符 s[i] 为结尾的最长有效括号的长度为 0,即 dp[i] = 0
5. 最终结果 #

根据我们之前定义的状态,dp[i] 表示为:以字符 s[i] 为结尾的最长有效括号的长度。则最终结果为 max(dp[i])

思路 1:代码 #

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def longestValidParentheses(self, s: str) -> int:
        dp = [0 for _ in range(len(s))]
        ans = 0
        for i in range(1, len(s)):
            if s[i] == '(':
                continue
            if s[i - 1] == '(':
                if i >= 2:
                    dp[i] = dp[i - 2] + 2
                else:
                    dp[i] = 2
            elif i - dp[i - 1] > 0 and s[i - dp[i - 1] - 1] == '(':
                if i - dp[i - 1] >= 2:
                    dp[i] = dp[i - 1] + dp[i - dp[i - 1] - 2] + 2
                else:
                    dp[i] = dp[i - 1] + 2
            ans = max(ans, dp[i])

        return ans

思路 1:复杂度分析 #

  • 时间复杂度:$O(n)$,其中 $n$ 为字符串长度。
  • 空间复杂度:$O(n)$。

思路 2:栈 #

  1. 定义一个变量 ans 用于维护最长有效括号的长度,初始时,ans = 0
  2. 定义一个栈用于判定括号对是否匹配(栈中存储的是括号的下标),栈底元素始终保持「最长有效括号子串的开始元素的前一个元素下标」。
  3. 初始时,我们在栈中存储 -1 作为哨兵节点,表示「最长有效括号子串的开始元素的前一个元素下标为 -1」,即 stack = [-1]
  4. 然后从左至右遍历字符串。
    1. 如果遇到左括号,即 s[i] == '(',则将其下标 i 压入栈,用于后续匹配右括号。
    2. 如果遇到右括号,即 s[i] == ')',则将其与最近的左括号进行匹配(即栈顶元素),弹出栈顶元素,与当前右括号进行匹配。弹出之后:
      1. 如果栈为空,则说明:
        1. 之前弹出的栈顶元素实际上是「最长有效括号子串的开始元素的前一个元素下标」,而不是左括号(,此时无法完成合法匹配。
        2. 将当前右括号的坐标 i 压入栈中,充当「下一个有效括号子串的开始元素前一个下标」。
      2. 如果栈不为空,则说明:
        1. 之前弹出的栈顶元素为左括号 (,此时可完成合法匹配。
        2. 当前合法匹配的长度为「当前右括号的下标 i」 - 「最长有效括号子串的开始元素的前一个元素下标」。即 i - stack[-1]
        3. 更新最长匹配长度 ansmax(ans, i - stack[-1])
  5. 遍历完输出答案 ans

思路 2:代码 #

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution:
    def longestValidParentheses(self, s: str) -> int:
        stack = [-1]
        ans = 0
        for i in range(len(s)):
            if s[i] == '(':
                stack.append(i)
            else:
                stack.pop()
                if stack:
                    ans = max(ans, i - stack[-1])
                else:
                    stack.append(i)
        return ans

思路 2:复杂度分析 #

  • 时间复杂度:$O(n)$,其中 $n$ 为字符串长度。
  • 空间复杂度:$O(n)$。

参考资料 #

本站总访问量  次  |  您是本站第  位访问者