LeetCode 921. Minimum Add to Make Parentheses Valid

921. Minimum Add to Make Parentheses Valid

921. Minimum Add to Make Parentheses Valid python solution

题目描述

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.

解析

需要找出’(‘和’)‘的对应关系，记录连续出现’(‘的次数，若此时出现‘)’，就说明有（）配对。计算在’(‘后‘)’多出现的次数，同理记录在‘)’后’('多出现的次数。两者的绝对值之和，就是需要添加的个数。

// An highlighted block
class Solution:
    def minAddToMakeValid(self, S: str) -> int:
        left=0
        right=0
        for i in S:
            if i=='(':
                left+=1
            elif left>=1:
                left-=1
            else: right+=1
        
        return left+right

Reference

https://leetcode.com/problems/minimum-add-to-make-parentheses-valid/discuss/420068/python-without-stack-beats-99