1541. Minimum Insertions to Balance a Parentheses String¶
题目信息¶
- 题号:
1541
- 难度:
Medium
- 主题:
字符串、括号匹配、贪心
- 原题:
- 重点:
每个左括号必须由连续两个右括号匹配;可在任意位置插入括号,求最少插入数
题目重述¶
给定只包含 ( 和 ) 的字符串 s。在本题的平衡规则中,每个左括号都必须对应其右侧连续出现的两个右括号 )),并且括号嵌套关系必须合法。
可以在字符串任意位置插入左括号或右括号。请返回使字符串满足上述规则所需的最少插入次数。
1 <= s.length <= 10^5。
自建示例¶
已经由一个左括号和两个右括号组成时无需插入:
输入:s = "())"
输出:0
解释:唯一左括号恰好由连续的两个右括号匹配。
孤立左括号需要补充两个右括号:
输入:s = "("
输出:2
解释:在末尾插入 "))" 后得到平衡字符串。