Python程序：查找给定字符串中最长有效括号的长度

假设我们有一个字符串 s。这个 s 只包含左括号和右括号。我们需要找到最长有效（格式正确）括号子字符串的长度。例如，如果输入是“))(())())”，则结果将是 6，因为有效的字符串是“(())()”。

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

创建一个栈，并插入 -1。设置 ans := 0
从 i=0 到字符串长度-1循环
- 如果 s[i] 是左括号，则将 i 插入栈中
- 否则
  - 如果栈不为空，且栈顶不为 -1，且 s[栈顶] 是左括号，则
    - 从栈中弹出栈顶元素
    - ans := ans 和 i - 栈顶元素中的最大值
  - 否则将 i 插入栈中
返回 ans

示例

让我们看看以下实现来更好地理解：

class Solution(object):
   def solve(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.solve("))(())())"))

输入

"))(())())"

输出

Arnab Chakraborty

更新于: 2020-12-22

95 次浏览

开启你的职业生涯

通过完成课程获得认证

开始学习