921. Minimum Add to Make Parentheses Valid

Tags: Medium Stack Greedy

Links: https://leetcode.com/problems/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.

---

class Solution {
public:
    int minAddToMakeValid(string S) {
        std::ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        cout.tie(NULL);

        int n = S.size();
        if (!n) return 0;
        int sum = 0;
        int cnt = 0;
        for (int i = 0; i < n; ++i) {
            if (S[i] == '(') ++sum;
            else --sum;

            if (sum < 0) {
                ++cnt; sum = 0;
            }
        }

        return cnt + sum;
    }
};

考虑特殊情况)))(((，可以类似32的贪心解法，那么只要出现负数就意味着)无法匹配，所以计数器+1。如果最后sum > 0，意味着有(不匹配，所以需要的个数就是两个部分的总和。

UVA 1626 是这道题的进一步拓展，考虑两种括号，并且要给出如何去添加的方案，是一个很好的深入。这道题如果单纯和LeetCode一样统计个数的话，其实只需要把[也看成(就好了，但是因为要输出如何补充，那么就是路径输出的问题了。