diff options
author | Jack Sangdahl <[email protected]> | 2024-10-08 18:26:55 -0600 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2024-10-08 18:26:55 -0600 |
commit | 0bc0cb90d1af8a72f45dfe7fe93025c368a2790d (patch) | |
tree | 3ef802850a5cded350f2691e3261f019647adee2 | |
parent | a0b333f1632860075e8bee17784777ec002c2197 (diff) | |
download | leetcode-0bc0cb90d1af8a72f45dfe7fe93025c368a2790d.tar.gz leetcode-0bc0cb90d1af8a72f45dfe7fe93025c368a2790d.zip |
921. minimum add to make parentheses valid
-rw-r--r-- | min_add_make_parenthese_valid.c | 30 | ||||
-rw-r--r-- | min_add_make_parenthese_valid.py | 33 |
2 files changed, 63 insertions, 0 deletions
diff --git a/min_add_make_parenthese_valid.c b/min_add_make_parenthese_valid.c new file mode 100644 index 0000000..f0b2fe3 --- /dev/null +++ b/min_add_make_parenthese_valid.c @@ -0,0 +1,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 +} diff --git a/min_add_make_parenthese_valid.py b/min_add_make_parenthese_valid.py new file mode 100644 index 0000000..f1f7acd --- /dev/null +++ b/min_add_make_parenthese_valid.py @@ -0,0 +1,33 @@ +# 921. Minimum Add to Make Parentheses Valid + +""" +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 +""" + + +class Solution(object): + def minAddToMakeValid(self, s): + """ + :type s: str + :rtype: int + """ + stack = [] + for i in s: + if stack: + if stack[-1] == "(" and i == ")": + stack.pop() + else: + stack.append(i) + else: + stack.append(i) + return len(stack) + + +if __name__ == "__main__": + obj = Solution() + print(obj.minAddToMakeValid(s="())")) + print(obj.minAddToMakeValid(s="(((")) |