Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
leetcode-stack
class Solution:
"""
Greedy+stack:
We use stack to keep track of index of unmatched left parentheses.
Top of stack is nearest index of unmatched left parenthese.
We traverse the given string forward.
when encounter the open parenthese, we append the index
when encounter the close parenthese,
if stack is empty, we need to remove current close parenthese to get valid paretheses
so, min_nb += 1
else:
# to balance the unmatched open parenthese
# use a removed_index hashset to store the index needed to be removed
stack.pop()
In the end, if our stack is not empty, means we need to removed all those unmatched left parenthese, to get valid paretheses.
while stack:
stack.pop()
min_nb += 1
"""
def minAddToMakeValid(self, S: str) -> int:
stack = collections.deque([])
min_nb = 0
for s in S:
if s is '(':
stack.append(1)
elif s is ')':
if len(stack) != 0:
stack.pop()
else:
min_nb+=1
while stack:
stack.pop()
min_nb+=1
return min_nb
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment