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:
AB
(A
concatenated with B
), where A
and B
are valid strings, or(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 <= 1000
S
only consists of '('
and ')'
characters.struct Solution;
impl Solution {
fn min_add_to_make_valid(s: String) -> i32 {
let mut stack: Vec<char> = vec![];
let mut res = 0;
for c in s.chars() {
match c {
'(' => {
stack.push(c);
}
')' => {
if stack.is_empty() {
res += 1;
} else {
stack.pop();
}
}
_ => {}
}
}
res + stack.len() as i32
}
}
#[test]
fn test() {
let s = "())".to_string();
let res = 1;
assert_eq!(Solution::min_add_to_make_valid(s), res);
let s = "(((".to_string();
let res = 3;
assert_eq!(Solution::min_add_to_make_valid(s), res);
let s = "()".to_string();
let res = 0;
assert_eq!(Solution::min_add_to_make_valid(s), res);
let s = "()))((".to_string();
let res = 4;
assert_eq!(Solution::min_add_to_make_valid(s), res);
}