【leetcode刷题】T29-使括号有效的最少添加个数

【英文题目】（学习英语的同时，更能理解题意哟~）

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: 

Example 2:

Input: "((("
Output: 

【中文题目】

给定一个由 '(' 和 ')' 括号组成的字符串 S，我们需要添加最少的括号（ '(' 或是 ')'，可以在任何位置），以使得到的括号字符串有效。

从形式上讲，只有满足下面几点之一，括号字符串才是有效的：

• 它是一个空字符串，或者
• 它可以被写成 AB （A 与 B 连接）, 其中 A 和 B 都是有效字符串，或者
• 它可以被写作 (A)，其中 A 是有效字符串。

给定一个括号字符串，返回为使结果字符串有效而必须添加的最少括号数。

示例 1：

输入："())"
输出：

示例 2：

输入："((("
输出：

【思路】

我们使用left、right分别统计多余的左括号和右括号，遇到左括号，left加1；遇到右括号，若left不为0，left减1，否则right加1（左括号不够，多的右括号才是多余的）。（代码中count、res代替left、right）

【代码】

python版本

class Solution(object):
    def minAddToMakeValid(self, S):
        """
        :type S: str
        :rtype: int
        """
        count = 
        res = 
        for si in S:
            if si == '(':
                count += 
            elif count == :
                res += 
            else:
                count -= 
        return res + count

C++版本

class Solution {
public:
    int minAddToMakeValid(string S) {
        int count = ;
        int res = ;
        for(char si:S){
            if(si == '('){
                count += ;
            }else{
                if(count == ){
                    res += ;
                }else
                    count -= ;
            }
        }
        return count + res;
    }
};