# [LeetCode] 921. Minimum Add to Make Parentheses Valid

2018/10/14 23:55

## Description

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.

## Analyse

1. 遇到(就计数器+1
2. 遇到)，如果之前还有(就直接消去一个(，否则就要增加一个(来抵消这个)

## Code

int minAddToMakeValid(string S)
{
int left_count = 0;
int total = 0;

for(char c : S)
{
if (c == '(')
{
++left_count;
++total;
}
else
{
if (left_count > 0)
{
--left_count;
--total;
}
else
{
++total;
}
}
}

}


## Result

4ms faster than 100.00%

0
0 收藏

0 评论
0 收藏
0