LeetCode-32. 最长有效括号【栈 字符串 动态规划】

LeetCode-32. 最长有效括号【栈 字符串 动态规划】

• 题目描述：
• 解题思路一：辅助栈
• 解题思路二：动态规划
• 解题思路三：0

  题目描述：

  给你一个只包含 ‘(’ 和 ‘)’ 的字符串，找出最长有效（格式正确且连续）括号

  子串

  的长度。

  示例 1：

  输入：s = “(()”

  输出：2

  解释：最长有效括号子串是 “()”

  示例 2：

  输入：s = “)()())”

  输出：4

  解释：最长有效括号子串是 “()()”

  示例 3：

  输入：s = “”

  输出：0

  提示：

  0 int: stack = [] res = 0 for i in range(len(s)): if not stack or s[i] == '(' or s[stack[-1]] == ')': stack.append(i) else: stack.pop() res = max(res, i - (stack[-1] if stack else -1)) return res

  时间复杂度：O(n)

  空间复杂度：O(n)

  解题思路二：动态规划

  

  class Solution:
      def longestValidParentheses(self, s: str) -> int:        
          maxans = 0
          dp = [0]*len(s)
          for i in range(len(s)):
              if s[i] == ")":
                  # 避免python负数的从后往前取值
                  if i - 1 = 2 else 0 ) + 2
                  elif i - dp[i - 1] > 0 and s[i - dp[i - 1] - 1] == "(":
                      dp[i] = dp[i - 1] + (dp[i - dp[i - 1] - 2] if i - dp[i - 1] >= 2 else 0) +2
                  maxans = max(maxans, dp[i])
          return maxans
  

  时间复杂度：O(n)

  空间复杂度：O(n)

  解题思路三：0

  时间复杂度：O(n)

  空间复杂度：O(n)