Python中最长的有效括号

  • Z时代
  • 2024-01-10
  • 分类：综合

假设我们有一个带括号的字符串。我们必须找到有效（格式正确）括号的最长长度。因此，如果输入类似“））（()）()），则结果将为6，因为有效字符串为“（()）()”。

为了解决这个问题，我们将遵循以下步骤-

  • 进行堆叠，然后插入-1。，设置ans：= 0

  • 对于i，范围为0到堆栈长度– 1

    • 如果堆栈不为空并且堆栈顶部不为-1并且s [stack top]是开括号，则

    • 否则将我插入堆栈

    • 堆栈中的顶部元素

    • ans：= ans和i的最大值–堆栈顶部

    • 如果s [i]是开括号，则将i插入堆栈

    • 除此以外

    • 返回ans

    示例

    让我们看下面的实现以更好地理解-

    class Solution(object):
       def longestValidParentheses(self, s):
          stack = [-1]
          ans = 0
          for i in range(len(s)):
             if s[i] == "(":
                stack.append(i)
             else:
                if stack and stack[-1]!=-1 and s[stack[-1]] == "(":
                   stack.pop()
                   ans = max(ans,i - stack[-1])
                else:
                stack.append(i)
          return ans
    ob = Solution()print(ob.longestValidParentheses("))(())())"))

    输入值

    "))(())())"

    输出结果

    6

    以上是 Python中最长的有效括号 的全部内容， 来源链接： utcz.com/z/322104.html

    回到顶部