921. Minimum Add to Make Parentheses Valid - cocoder39/coco39_LC GitHub Wiki

921. Minimum Add to Make Parentheses Valid

Option 1: stack

class Solution:
    def minAddToMakeValid(self, s: str) -> int:
        stack = []
        for ch in s:
            if ch == '(':
                stack.append(ch)
            elif ch == ')':
                if stack and stack[-1] == '(':
                    stack.pop()
                else:
                    stack.append(ch)
        return len(stack)

Option 2: get rid of stack

class Solution:
    def minAddToMakeValid(self, s: str) -> int:        
        left, right = 0, 0
        for ch in s:
            if ch == '(':
                left += 1
            elif ch == ')':                    
                if left > 0:
                    left -= 1
                else:
                    right += 1
        return left + right