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, orIt can be written as AB (A concatenated with B), where A and B are valid strings, orIt 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:

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

---

题目：添加最少数量的括弧使得括弧对合法。

思路：贪心算法，参见Approach 1: Balance。用balance表示前i个字符中孤立的(个数。当遇到的字符为(，balance加1，遇到的字符为)，balance减1，如果balance小于0，那么我们知道必须要在该位置（之前）添加一个(才能使得括号对合法。所有字符循环完后，再加上balance个)来平衡多出的(。

工程代码下载

class Solution { public: int minAddToMakeValid(string S) { int balance = 0, res = 0; for(auto c : S){ if(c == ')'){ balance -= 1; if(balance == -1){ res += 1; balance = 0; } } else{ balance += 1; } } return res + balance; } };