blob: f0b2fe3193b7731dcd6b60f9d83b5de11af521d7 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
|
// 921. Minimum Add to Make Parentheses Valid
#include "leetcode.h"
/*
* a parentheses string is valid if and only if it is empty string, 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. you are given a parentheses
* string 's'. in one move you can insert a parentheses at any position of the
* string. return the minimum number of moves required to make 's' valid
*/
int minAddToMakeValid(char *s) {
int open = 0, close = 0, n = strlen(s);
for (int i = 0; i < n; i++)
if (s[i] == '(')
open++;
else {
if (open)
open--;
else
close++;
}
return open + close;
}
int main() {
char *s1 = "())", *s2 = "(((";
printf("%d\n", minAddToMakeValid(s1)); // expect: 1
printf("%d\n", minAddToMakeValid(s2)); // expect: 3
}
|