aboutsummaryrefslogtreecommitdiff
path: root/min_add_make_parenthese_valid.py
diff options
context:
space:
mode:
Diffstat (limited to 'min_add_make_parenthese_valid.py')
-rw-r--r--min_add_make_parenthese_valid.py33
1 files changed, 33 insertions, 0 deletions
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="((("))