From 0bc0cb90d1af8a72f45dfe7fe93025c368a2790d Mon Sep 17 00:00:00 2001 From: Jack Sangdahl Date: Tue, 8 Oct 2024 18:26:55 -0600 Subject: 921. minimum add to make parentheses valid --- min_add_make_parenthese_valid.c | 30 ++++++++++++++++++++++++++++++ min_add_make_parenthese_valid.py | 33 +++++++++++++++++++++++++++++++++ 2 files changed, 63 insertions(+) create mode 100644 min_add_make_parenthese_valid.c create mode 100644 min_add_make_parenthese_valid.py 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="(((")) -- cgit v1.2.3