使用 Python 查找最小插入以平衡括号字符串的程序
假设我们有一个带有左括号和右括号'('和')'的字符串s。我们可以说括号字符串在以下情况下是平衡的-
任何左括号'('都有一个对应的两个连续的右括号'))'。
左括号'('必须放在相应的两个连续右括号'))'之前。
例如,“())”、“())(()))”是平衡的,但“)()”、“()))”不是。如果我们有这样的字符串,我们必须计算括号(开头或结尾)的数量以使字符串平衡。
所以,如果输入像s="(())))))",那么输出将是1,因为如果我们把它分开,我们可以得到"(())))))",所以我们需要一个左括号使字符串"(())())))"使其平衡。
为了解决这个问题,我们将按照以下步骤操作-
:=0,n:=s的大小
返回:=0,我:=0
当i
如果s[i]与'('相同,则
:=o+1
如果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))
输入
"(())))))"输出结果
3