0921. Minimum Add to Make Parentheses Valid

题目信息

题号:

0921

难度:

Medium

主题:

字符串、括号匹配、最少插入

原题:

LeetCode 0921

重点:

每次可以在任意位置插入一个左括号或右括号;需要使全部括号正确配对并返回最少插入次数

题目重述

给定只包含 '(' 和 ')' 的字符串 s。一次操作可以在字符串的任意位置插入一个左括号或一个右括号。

合法括号字符串要求每个右括号都有位于其左侧且尚未配对的左括号,并且最终所有左括号也都被配对。请返回把 s 变为合法括号字符串所需的最少插入次数。

1 <= s.length <= 1000。

自建示例

同时存在多余右括号和未闭合左括号:

输入:s = "())(()"
输出:2
解释:第三个字符 ')' 缺少可配对的左括号,末尾还剩一个未闭合的左括号。分别补入一个 '(' 和一个 ')' 即可。

字符串已经合法:

输入:s = "()"
输出:0
解释:唯一一对括号已经正确配对,不需要插入任何字符。