LeetCode 1249. Minimum Remove to Make Valid Parentheses - FB高频题1

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. 

Example 2:

Input: s = "a)b(c)d" Output: "ab(c)d" 

Example 3:

Input: s = "))((" Output: "" Explanation: An empty string is also valid.

Constraints:

• 1 <= s.length <= 105
• s[i] is either'(' , ')', or lowercase English letter.

题目说给定一个字符串包含英文字母和左右小括号'('和‘)’，字符串里的左右小括号有可能是不匹配的，要求移除最少个数的左右小括号使得剩下的是完全匹配的，返回移除后的有效字符串。

首先要搞清楚左右小括号的匹配原则，当遇到一个左括号时，后面必须要有一个右括号才能匹配，要是直到最后也没出现右括号则该左括号为无效需被删除；当遇到一个右括号时，其前面必须要有一个等着匹配的左括号，否则该右括号为无效需要被删除。

由此可见，整个删除过程是基于左括号的，因此可以用一个堆栈来记录待匹配的左括号，从头到尾扫一遍字符串，当遇到左括号就把左括号放入堆栈里（堆栈里放的是当前左括号的位置）；当遇到右括号时，就判断此时堆栈是否为空，如不为空则从堆栈顶弹出一个左括号与其匹配，如为空表示该右括号需要被删除。按此方法直到遍历结束，结束后堆栈里剩下的左括号也都是要被删除的。在整个过程中用一个set来记录要被删除的括号的位置，最后再遍历一遍统一删除，这样效率会比较高。

class Solution:
    def minRemoveToMakeValid(self, s: str) -> str:
        rm = set()
        st = []
        for i,c in enumerate(s):
            if c == '(':
                st.append(i)
            elif c == ')':
                if not st:
                    rm.add(i)
                else:
                    st.pop()
        while st:
            rm.add(st.pop())
        res = []
        for i,c in enumerate(s):
            if i not in rm:
                res.append(c)
        
        return ''.join(res)