aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2024-10-08 18:26:55 -0600
committerJack Sangdahl <[email protected]>2024-10-08 18:26:55 -0600
commit0bc0cb90d1af8a72f45dfe7fe93025c368a2790d (patch)
tree3ef802850a5cded350f2691e3261f019647adee2
parenta0b333f1632860075e8bee17784777ec002c2197 (diff)
downloadleetcode-0bc0cb90d1af8a72f45dfe7fe93025c368a2790d.tar.gz
leetcode-0bc0cb90d1af8a72f45dfe7fe93025c368a2790d.zip
921. minimum add to make parentheses valid
-rw-r--r--min_add_make_parenthese_valid.c30
-rw-r--r--min_add_make_parenthese_valid.py33
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="((("))