aboutsummaryrefslogtreecommitdiff
path: root/min_add_make_parenthese_valid.py
blob: f1f7acda08c23e3fdd2fd45ad92c7903c930f8ac (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
31
32
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="((("))