使用 Python 查找最小插入以平衡括号字符串的程序

Z时代
2024-01-10
分类：综合

假设我们有一个带有左括号和右括号 '(' 和 ')' 的字符串 s。我们可以说括号字符串在以下情况下是平衡的 -

任何左括号'('都有一个对应的两个连续的右括号'))'。
左括号 '(' 必须放在相应的两个连续右括号 '))' 之前。

例如，“())”、“())(()))”是平衡的，但“)()”、“()))”不是。如果我们有这样的字符串，我们必须计算括号（开头或结尾）的数量以使字符串平衡。

所以，如果输入像 s = "(())))))"，那么输出将是 1，因为如果我们把它分开，我们可以得到 "(()) ))))"，所以我们需要一个左括号使字符串 "( ()) ()) ))" 使其平衡。

为了解决这个问题，我们将按照以下步骤操作 -

:= 0, n := s 的大小
返回：= 0，我：= 0
当 i < n 时，做

如果 s[i] 与 '(' 相同，则

:= o + 1

如果 i + 1 < n 且 s[i + 1] 与 ')' 相同，则
ret := ret + 1
如果 o 是 0，那么
否则，
否则，

:= o - 1

ret := ret + 1
如果 o 是 0，那么
否则，
ret := ret + 1
我 := 我 + 1
否则，

:= o - 1

我 := 我 + 1

返回 ret + 2 * o

让我们看看以下实现以获得更好的理解 -

示例

def solve(s):
   o = 0
   n = len(s)
   ret = 0
   i = 0
   while i < n:
      if s[i] == '(':
         o += 1
      else:
         if i + 1 < n and s[i + 1] == ')':
            if not o:
               ret += 1
            else:
               o -= 1
               i += 1
         else:
            ret += 1
            if not o:
               ret += 1
            else:
               o -= 1
      i += 1
   return ret + 2 * o
s = "(())))))"
print(solve(s))