921. Minimum Add to Make Parentheses Valid

Question 921

https://leetcode.com/problems/minimum-add-to-make-parentheses-valid/description/

Given a string S of '(' and ')' parentheses, we add the minimum number of parentheses ( '(' or ')', and in any positions ) so that the resulting parentheses string is valid.

Formally, a parentheses string is valid if and only if:

• It is the empty string, or

• 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.

Given a parentheses string, return the minimum number of parentheses we must add to make the resulting string valid.

Example 1:

Input: "())"
Output: 1

Answer

v1

class Solution(object):
    def minAddToMakeValid(self, S):

        Sstack = []
        Wrong = []
        for s in S:
            if s == "(":
                Sstack.append(s)
            elif s == ")":
                if len(Sstack) < 1:
                    Wrong.append(s)
                else:
                    Sstack.pop()
        
        return len(Sstack) + len(Wrong)

v2

class Solution(object):
    def minAddToMakeValid(self, S):

        Sstack = 0
        Wrong = 0
        for s in S:
            if s == "(":
                Sstack += 1
            elif s == ")":
                if Sstack < 1:
                    Wrong += 1
                else:
                    Sstack -= 1
        
        return Sstack + Wrong