首页 > 试题广场 >

平衡括号字符串的最少插入次数

[编程题]平衡括号字符串的最少插入次数
  • 热度指数:45 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解

给你一个括号字符串 s ,它只包含字符 '('和 ')' 。一个平衡的括号字符串满足:

  1. 任何左括号 '(' 必须对应两个连续的右括号 '))' 。
  2. 左括号 '(' 必须在对应的连续两个右括号 '))' 之前。

比方说 "())", "())(())))"和 "(())())))" 都是平衡的, ")()", "()))"和 "(()))" 都是不平衡的。

你可以在任意位置插入字符'('和')'使字符串平衡。

请你返回让s 平衡的最少插入次数。

(*试卷编程题,请选择2道(共计3道)作答,多答将取前2个最高分计算得分。

示例1

输入

"(()))"

输出

1

说明

第二个左括号有与之匹配的两个右括号,但是第一个左括号只有一个右括号。我们需要在字符串结尾额外增加一个')'使字符串变成平衡字符串"(())))" 

示例2

输入

"())"

输出

0

说明

字符串已经平衡了。

示例3

输入

"(((((("

输出

12

说明

添加12个')'得到平衡字符串。


备注:
s 只包含 '(' 和 ')' 。

这道题你会答吗?花几分钟告诉大家答案吧!