Python中使括号有效所需的最小添加

假设我们有一个包含 '(' 和 ')' 括号的字符串 S，我们需要在任意位置添加最少的括号，以便生成的括号字符串有效。当且仅当满足以下条件时，括号字符串才有效：

  • 它是空字符串
  • 它可以写成 XY（X 与 Y 连接），其中 X 和 Y 是有效的字符串
  • 它可以写成 (A)，其中 A 是一个有效的字符串。

因此，如果字符串类似于 "()))((", 则我们需要添加 4 个括号才能使字符串有效。

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

  • 如果 S 为空，则返回 0
  • 计数器 count := 0，temp 为一个数组，临时计数器 temp_counter := 0
  • 对于 S 中的每个 i
    • 如果 i 是左括号，则将 i 插入 temp
    • 否则
      • 当 temp 的长度 > 0 且最后一个元素是左括号时，删除 temp 的最后一个元素，否则将 i 插入 temp
  • 返回 temp 的大小。

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

示例

在线演示

class Solution:
   def minAddToMakeValid(self, S):
      if not S:
         return 0
      count = 0
      temp = []
      temp_counter = 0
      for i in S:
         if i =='(':
            temp.append(i)
         else:
            if len(temp)>0 and temp[len(temp)-1] =='(':
               temp.pop(len(temp)-1)
            else:
               temp.append(i)
      return len(temp)
ob = Solution()
print(ob.minAddToMakeValid("()))(("))

输入

"()))(("

输出

4

更新于：2020年4月30日

浏览量 338

开启你的职业生涯

完成课程获得认证

开始学习
广告