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

假设我们有一个字符串“（”和“）”作为圆括号，我们在任意位置加上最小的圆括号，这样得到的圆括号字符串就是有效的。仅当且仅当-时，括号字符串才有效-

• 这是空字符串

• 可以写为XY（X与Y串联），其中X和Y是有效字符串

• 它可以表示为(A)，其中A是有效字符串。

因此，如果字符串类似于“（()））（（”，那么我们需要再添加4个括号以使字符串有效。

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

• 如果S为空，则返回0

• count：= 0，temp是一个数组，temp_counter：= 0

• 为了我在S

• 当temp的长度> 0并且的最后一个元素在括号中时，则删除temp的最后一个元素，否则将i插入temp

• 如果我打开括号，则将我插入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