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 withB
), whereA
andB
are valid strings, or - It can be written as
(A)
, whereA
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 <= 1000
-
S
only consists of'('
and')'
characters.
Approach #1: C++.[stack]
class Solution {
public:
int minAddToMakeValid(string S) {
int len = S.length();
if (len == 0) return 0;
stack<char> myStack;
myStack.push(S[0]); for (int i = 1; i < len; ++i) {
if (myStack.empty()) myStack.push(S[i]);
else if (myStack.top() == '(' && S[i] == ')') myStack.pop();
else myStack.push(S[i]);
} return myStack.size();
}
};