LeetCode 1249. 移除无效的括号 中等 ​

题目描述 ​

给你一个由 '('、')' 和小写字母组成的字符串 s。

你需要从字符串中删除最少数目的 '(' 或者 ')' （可以删除任意位置的括号)，使得剩下的「括号字符串」有效。

请返回任意一个合法字符串。

有效「括号字符串」应当符合以下 任意一条 要求：

空字符串或只包含小写字母的字符串可以被写作 AB（A 连接 B）的字符串，其中 A 和 B 都是有效「括号字符串」可以被写作 (A) 的字符串，其中 A 是一个有效的「括号字符串」

示例 1：

输入：s = "lee(t(c)o)de)"
输出："lee(t(c)o)de"
解释："lee(t(co)de)" , "lee(t(c)ode)" 也是一个可行答案。

示例 2：

输入：s = "a)b(c)d"
输出："ab(c)d"

示例 3：

输入：s = "))(("
输出：""
解释：空字符串也是有效的

示例 4：

输入：s = "(a(b(c)d)"
输出："a(b(c)d)"

提示：

1 <= s.length <= 10^5
s[i] 可能是 '('、')' 或英文小写字母

来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/minimum-remove-to-make-valid-parentheses 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路 ​

一开始我是想着只要对应括号匹配就好了，将多余的右括号删掉，但是这个样例 ))(( 不可能过的，因为左括号也可以不匹配呀。于是我想着将括号对应字符串索引存起来，起初我们可以将不匹配的右括号还是按原来方法删掉就好了，匹配一个就删掉一个对应左括号的索引值，最后多出来的索引值全删掉就好了，这样就不会出现左括号还余留的情况。

这里提示一下：不要用 splice去删除指定下标的元素，splice会改变原数组长度，而你原本存的下标是基于原数组的。 delete方法不会改变数组长度，但删除的那个位置会变成'undefined'，所以我们用fliter方法过滤一遍出有效值 arr=arr.filter(item=>item)

最后通过 res.join('') 方法，将数组转换成我们最后要的字符串即可。

var minRemoveToMakeValid = function (s) {
  let res = [...s];
  let stack = [];
  for (let i = -0; i < s.length; i++) {
    let ch = s[i];
    if (ch === "(") {
      stack.push(i);
    } else if (ch === ")") {
      if (stack.length) stack.pop();
      else delete res[i];
    }
  }
  while (stack.length) {
    let idx = stack.pop();
    delete res[idx];
  }
  res = res.filter((item) => item);
  return res.join("");
};

class Solution {
public:
    string minRemoveToMakeValid(string s) {
        stack<int> st;
        for (int i = 0; i < s.size(); i++) {
            if (s[i] == '(') {
                st.push(i);
            } else if (s[i] == ')') {
                if (!st.empty()) {
                    st.pop();
                } else {
                    s[i] = '*';
                }
            }
        }
        while (!st.empty()) {
            s[st.top()] = '*';
            st.pop();
        }
        s.erase(remove(s.begin(), s.end(), '*'), s.end());
        return s;
    }
};

class Solution {
    public String minRemoveToMakeValid(String s) {
        StringBuilder sb = new StringBuilder(s);
        Stack<Integer> st = new Stack<>();
        for (int i = 0; i < sb.length(); i++) {
            if (sb.charAt(i) == '(') {
                st.push(i);
            } else if (sb.charAt(i) == ')') {
                if (!st.isEmpty()) {
                    st.pop();
                } else {
                    sb.setCharAt(i, '*');
                }
            }
        }
        while (!st.isEmpty()) {
            sb.setCharAt(st.pop(), '*');
        }
        return sb.toString().replaceAll("\\*", "");
    }
}

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

学如逆水行舟，不进则退