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="((("))
|