Skip to content

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

作者:Choi Yang
更新于:6 个月前
字数统计:795 字
阅读时长:3 分钟
阅读量:

题目描述

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

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

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

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

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

示例 1:

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

示例 2:

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

示例 3:

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

示例 4:

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

提示:

javascript
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('') 方法,将数组转换成我们最后要的字符串即可。

javascript
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("");
};
cpp
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;
    }
};
java
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("\\*", "");
    }
}
python
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('*', '')
javascript
学如逆水行舟,不进则退

Contributors

Choi Yang