Python程序：计算使字符串正确的最小无效括号移除数量

假设我们有一个括号字符串；我们需要编写一个函数来计算需要移除的最小括号数量，以使字符串正确（每个左括号最终都会被右括号闭合）。

因此，如果输入类似于 "(()))("，则输出将为 2，因为正确的字符串是 "(())"，移除 ")("。

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

  • total := 0, temp := 0
  • 对于s中的每个字符p，执行以下操作
    • 如果p与"("相同，则
      • total := total + 1
    • 否则，当p与")"相同且total不为0时，则
      • total := total - 1
    • 否则，
      • temp := temp + 1
  • 返回 total + temp

让我们看看以下实现，以便更好地理解 -

示例

 在线演示

class Solution:
   def solve(self, s):
      total = 0
      temp = 0
      for p in s:
         if p == "(":
            total += 1
         elif p == ")" and total:
            total -= 1
         else:
            temp += 1
      return total + temp
ob1 = Solution()
string = "(()))("
print(ob1.solve(string))

输入

"(()))("

输出

2

更新于: 2020年10月20日

383 次浏览

开启你的 职业生涯

通过完成课程获得认证

开始学习
广告