LeetCode 1249 solution

problem

Given a string s of '(' , ')' and lowercase English characters.

Your task is to remove the minimum number of parentheses ('(' or ')', in any positions) so that the resulting parentheses string is valid and return any valid string.

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

• It is the empty string, contains only lowercase characters, 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.

Example 1:

• Input: s = "lee(t(c)o)de)"
• Output: "lee(t(c)o)de"
• Explanation: "lee(t(co)de)" , "lee(t(c)ode)" would also be accepted.

python

class Solution:
    def minRemoveToMakeValid(self, s: str) -> str:
        s = list(s)
        stack = []
        for i, char in enumerate(s):
            if char == '(':
                stack.append(i)
            elif char == ')':
                if stack:
                    stack.pop()
                else:
                    s[i] = ''
        while stack:
            s[stack.pop()] = ''
        return ''.join(s)

stack을 사용하면서 동시에 index를 사용해서 없애는 로직이다. ) 인 경우들은 for문에서 처리를 하고, 그 다음에 남은 ( 짝이 안 맞는 것들은 while 문을 돌면서 해결하게 된다. dope!