921. Minimum Add to Make Parentheses Valid

Given a string S of '(' and ')' parentheses, we add the minimum number of parentheses ( '(' or ')', and in any positions ) so that the resulting parentheses string is valid.

Formally, a parentheses string is valid if and only if:

  • It is the empty string, or
  • It can be written as AB (A concatenated with B), where A and B are valid strings, or
  • It can be written as (A), where A is a valid string.

Given a parentheses string, return the minimum number of parentheses we must add to make the resulting string valid.

Example 1:

Input: "())"
Output: 1

Example 2:

Input: "((("
Output: 3

Example 3:

Input: "()"
Output: 0

Example 4:

Input: "()))(("
Output: 4

Note:

  1. S.length <= 1000
  2. S only consists of '(' and ')' characters.

这道题给了一个括号字符串,可能是非法的,让我们补充最少数量的半括号,使其变为合法的括号字符串。那么实际上只要统计出需要添加的左右括号个数即可,这里使用两个变量 left 和 right,分别表示需要的左右括号个数。遍历字符串S,若遇到左括号,说明此时需要右括号,则 right 自增1;若遇到了右括号,若此时 right 大于0,说明当前的右括号可以用来匹配之前的左括号,不需要另加右括号,所以此时 right 自减1;而若此时 right 为0,说明当前的右括号前面没有左括号可以跟其匹配,则此时 left 自增1,表示需要额外的左括号。最后返回 left+right 即为所求,参见代码如下:
解法一:

class Solution {
public:
    int minAddToMakeValid(string S) {
        int left = 0, right = 0;
        for (char c : S) {
            if (c == '(') {
                ++right;
            } else if (right > 0) {
                --right;
            } else {
                ++left;
            }
        }
        return left + right;
    }
};

我们可以只用一个变量 cnt,表示当前左括号的个数。遍历字符串S,当遇到左括号,而此时 cnt 为负数时,表示此时右括号是多余左括号的,而当前遇到的左括号不能匹配之前的右括号,所以将 cnt 的绝对值加到结果 res 中,表示需要这多么的左括号来匹配之前多出的右括号。然后此时 cnt 自增1,因为当前遇到的是左括号,若当前遇到右括号,则 cnt 自减1,最终返回 res 加上 cnt 的绝对值即为所求,参见代码如下:
解法二:

class Solution {
public:
    int minAddToMakeValid(string S) {
        int res = 0, cnt = 0;
        for (char c : S) {
            if (c == '(') {
                if (cnt < 0) {
                    res += abs(cnt);
                    cnt = 0;
                }
                ++cnt;
            } else {
                --cnt;
            }
        }
        return res + abs(cnt);
    }
};

Github 同步地址:

https://github.com/grandyang/leetcode/issues/921

类似题目:

Remove Invalid Parentheses

Different Ways to Add Parentheses

Longest Valid Parentheses

Generate Parentheses

Valid Parentheses

参考资料:

https://leetcode.com/problems/minimum-add-to-make-parentheses-valid/

https://leetcode.com/problems/minimum-add-to-make-parentheses-valid/discuss/181132/C%2B%2BJavaPython-Straight-Forward-One-Pass

https://leetcode.com/problems/minimum-add-to-make-parentheses-valid/discuss/181086/Java-two-one-pass-7-liners-space-O(n)-and-O(1)-respectively

LeetCode All in One 题目讲解汇总(持续更新中…)


转载请注明来源于 Grandyang 的博客 (grandyang.com),欢迎对文章中的引用来源进行考证,欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论,也可以邮件至 grandyang@qq.com

💰


微信打赏


Venmo 打赏

(欢迎加入博主的知识星球,博主将及时答疑解惑,并分享刷题经验与总结,试运营期间前五十位可享受半价优惠~)

×

Help us with donation