Python程序：查找最长平衡子序列的长度

假设我们有一个包含括号 "(" 和 ")" 的字符串 s，我们需要找到最长平衡括号子序列的长度。

例如，如果输入是 s = "())(()("，则输出为 4，因为我们可以选择 "()()" 作为子序列。

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

  • res := 0

  • n := s 的长度

  • close := 0

  • for i in range(n - 1, -1, -1):

    • if s[i] == ")": then

      • close := close + 1

    • else:

      • if close > 0: then

        • close := close - 1

        • res := res + 2

  • return res

让我们来看下面的实现，以便更好地理解：

示例

 在线演示

class Solution:
   def solve(self, s):
      res = 0
      n = len(s)
      close = 0
      for i in range(n - 1, -1, -1):
         if s[i] == ")":
            close += 1
         else:
            if close > 0:
               close -= 1
                  res += 2
            return res
ob = Solution()
s = "())(()("
print(ob.solve(s))

输入

"())(()("

输出

4

更新于：2020年10月10日

311 次浏览

开启您的职业生涯

完成课程获得认证

开始学习
广告