[LeetCode] 1249. Minimum Remove to Make Valid Parentheses

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.

移除无效的括号。

给你一个由 '('、')' 和小写字母组成的字符串 s。 你需要从字符串中删除最少数目的 '(' 或者 ')' (可以删除任意位置的括号),使得剩下的「括号字符串」有效。 请返回任意一个合法字符串。

有效「括号字符串」应当符合以下 任意一条 要求:
空字符串或只包含小写字母的字符串
可以被写作 AB(A 连接 B)的字符串,其中 A 和 B 都是有效「括号字符串」
可以被写作 (A) 的字符串,其中 A 是一个有效的「括号字符串」

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

思路

思路是 stack 但是这个题跟20题 valid parenthesis 还不太一样,因为不光是判断,而是最后需要返回一个有效的结果。这个题我没有用到 stack 但是用到了 stack 的思想,用一个 open 变量判断到底是左括号多还是右括号多,如果 open 小于0(右括号多)就一定不要再放右括号了。

第一次扫描 input,从左往右,append 其他字符的同时,注意不要多 append 右括号即可,也就是说如果左括号都被抵消完之后又出现右括号,则不要放入结果;第二次从右往左 scan 第一次的结果,但是因为第一次扫描的时候只是控制不能让右括号多于左括号,这时有可能左括号是有多余的,所以在第二次从右往左扫描的时候需要判断如果左括号 left 多了,就不要再加入结果集了。

复杂度

时间O(n)
空间O(n)

代码

Java实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public String minRemoveToMakeValid(String s) {
StringBuilder sb = new StringBuilder();
int open = 0;
for (char c : s.toCharArray()) {
if (c == '(') {
open++;
} else if (c == ')') {
if (open == 0) {
continue;
}
open--;
}
sb.append(c);
}

StringBuilder res = new StringBuilder();
for (int i = sb.length() - 1; i >= 0; i--) {
if (sb.charAt(i) == '(' && open-- > 0) {
continue;
}
res.append(sb.charAt(i));
}
return res.reverse().toString();
}
}

[LeetCode] 1249. Minimum Remove to Make Valid Parentheses
https://shurui91.github.io/posts/2743385074.html
Author
Aaron Liu
Posted on
May 8, 2020
Licensed under