在 Python 中，添加最少数量的括号使括号有效
pythonserver side programmingprogramming
假设我们有一个由 '(' 和 ')' 括号组成的字符串 S，我们在任意位置添加最少数量的括号，以使生成的括号字符串有效。括号字符串当且仅当 − 时才有效
- 它是空字符串
- 它可以写成 XY(X 与 Y 连接)，其中 X 和 Y 是有效字符串
- 它可以写成 (A)，其中 A 是有效字符串。
因此，如果字符串类似于 "()))(("，则我们需要再添加 4 个括号才能使字符串有效。
要解决这个问题，我们将遵循以下步骤 −
- 如果 S 为空，则返回 0
- count := 0，temp 是一个数组，temp_counter := 0
- for i in S
- 如果 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
