minimum_remove_to_make_valid_parentheses
1# @leet start 2class Solution: 3 def minRemoveToMakeValid(self, s: str) -> str: 4 """ 5 This question asks us to remove items from the string that would 6 lead to unbalanced parentheses, and to return a string that has balanced 7 parentheses. 8 9 We can do this by going through the string with the valid parentheses 10 algorithm, but also keeping the indexes in the stack. If we see an '(', 11 we add the index to the stack. If we see a ')', we pop from the stack if 12 it's non-empty, closing a paren, or, we have an extra paren, so we have 13 to skip it when we iterate through the string again, so we add it to a 14 set of indexes to skip. 15 16 At the end of the iteration, we have a set of indexes in the stack that 17 are for superfluous open parens, so we add that to the indexes to remove 18 as well. 19 20 Finally, we iterate through the string, and if our current index is in 21 the set to remove, we don't add it to the final string. 22 """ 23 stack = [] 24 to_remove = set() 25 26 for i, c in enumerate(s): 27 if c == "(": 28 stack.append(i) 29 elif c == ")": 30 if not stack: 31 to_remove.add(i) 32 else: 33 stack.pop() 34 for i in stack: 35 to_remove.add(i) 36 res = ("" if i in to_remove else c for i, c in enumerate(s)) 37 return "".join(res) 38 39 40# @leet end 41 42 43def test(): 44 assert 2 + 2 == 4
class
Solution:
3class Solution: 4 def minRemoveToMakeValid(self, s: str) -> str: 5 """ 6 This question asks us to remove items from the string that would 7 lead to unbalanced parentheses, and to return a string that has balanced 8 parentheses. 9 10 We can do this by going through the string with the valid parentheses 11 algorithm, but also keeping the indexes in the stack. If we see an '(', 12 we add the index to the stack. If we see a ')', we pop from the stack if 13 it's non-empty, closing a paren, or, we have an extra paren, so we have 14 to skip it when we iterate through the string again, so we add it to a 15 set of indexes to skip. 16 17 At the end of the iteration, we have a set of indexes in the stack that 18 are for superfluous open parens, so we add that to the indexes to remove 19 as well. 20 21 Finally, we iterate through the string, and if our current index is in 22 the set to remove, we don't add it to the final string. 23 """ 24 stack = [] 25 to_remove = set() 26 27 for i, c in enumerate(s): 28 if c == "(": 29 stack.append(i) 30 elif c == ")": 31 if not stack: 32 to_remove.add(i) 33 else: 34 stack.pop() 35 for i in stack: 36 to_remove.add(i) 37 res = ("" if i in to_remove else c for i, c in enumerate(s)) 38 return "".join(res)
def
minRemoveToMakeValid(self, s: str) -> str:
4 def minRemoveToMakeValid(self, s: str) -> str: 5 """ 6 This question asks us to remove items from the string that would 7 lead to unbalanced parentheses, and to return a string that has balanced 8 parentheses. 9 10 We can do this by going through the string with the valid parentheses 11 algorithm, but also keeping the indexes in the stack. If we see an '(', 12 we add the index to the stack. If we see a ')', we pop from the stack if 13 it's non-empty, closing a paren, or, we have an extra paren, so we have 14 to skip it when we iterate through the string again, so we add it to a 15 set of indexes to skip. 16 17 At the end of the iteration, we have a set of indexes in the stack that 18 are for superfluous open parens, so we add that to the indexes to remove 19 as well. 20 21 Finally, we iterate through the string, and if our current index is in 22 the set to remove, we don't add it to the final string. 23 """ 24 stack = [] 25 to_remove = set() 26 27 for i, c in enumerate(s): 28 if c == "(": 29 stack.append(i) 30 elif c == ")": 31 if not stack: 32 to_remove.add(i) 33 else: 34 stack.pop() 35 for i in stack: 36 to_remove.add(i) 37 res = ("" if i in to_remove else c for i, c in enumerate(s)) 38 return "".join(res)
This question asks us to remove items from the string that would lead to unbalanced parentheses, and to return a string that has balanced parentheses.
We can do this by going through the string with the valid parentheses algorithm, but also keeping the indexes in the stack. If we see an '(', we add the index to the stack. If we see a ')', we pop from the stack if it's non-empty, closing a paren, or, we have an extra paren, so we have to skip it when we iterate through the string again, so we add it to a set of indexes to skip.
At the end of the iteration, we have a set of indexes in the stack that are for superfluous open parens, so we add that to the indexes to remove as well.
Finally, we iterate through the string, and if our current index is in the set to remove, we don't add it to the final string.
def
test():