class Solution {
public:
string minRemoveToMakeValid(string s) {
}
};
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 = "))(("
输出：""
解释：空字符串也是有效的
提示：
1 <= s.length <= 105s[i] 可能是 '('、')' 或英文小写字母原站题解
python3 解法, 执行用时: 80 ms, 内存消耗: 16.4 MB, 提交时间: 2022-12-04 12:09:04
class Solution:
def minRemoveToMakeValid(self, s: str) -> str:
st, s = [], list(s)
for i in range(len(s)):
# 如果为左括号，入栈
if s[i] == '(': st.append(i)
elif s[i] == ')':
# 如果栈中有左括号，此时两括号匹配，弹出前者
if st: st.pop()
# 如果没有左括号，那说明该右括号多了，需删除，该位子变成空字符串
else: s[i] = ''
# 遍历完成后，在栈中多余的左括号需删除
for i in st: s[i] = ''
return ''.join(s)
python3 解法, 执行用时: 80 ms, 内存消耗: 16.1 MB, 提交时间: 2022-12-04 12:06:28
class Solution:
def minRemoveToMakeValid(self, s: str) -> str:
left, right, ans = 0, s.count(')'), ''
for c in s:
if c == '(':
if right > 0:
ans += c
left += 1
right -= 1 # 消耗一个对应的右括号
elif c == ')':
if left > 0:
ans += c
left -= 1
else:
right -= 1 # 无效的右括号
else:
ans += c
return ans
java 解法, 执行用时: 35 ms, 内存消耗: 42.4 MB, 提交时间: 2022-12-04 12:05:45
class Solution {
public String minRemoveToMakeValid(String s) {
Set<Integer> indexesToRemove = new HashSet<>();
Stack<Integer> stack = new Stack<>();
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == '(') {
stack.push(i);
} if (s.charAt(i) == ')') {
if (stack.isEmpty()) {
indexesToRemove.add(i);
} else {
stack.pop();
}
}
}
// Put any indexes remaining on stack into the set.
while (!stack.isEmpty()) indexesToRemove.add(stack.pop());
StringBuilder sb = new StringBuilder();
for (int i = 0; i < s.length(); i++) {
if (!indexesToRemove.contains(i)) {
sb.append(s.charAt(i));
}
}
return sb.toString();
}
}
java 解法, 执行用时: 23 ms, 内存消耗: 42.1 MB, 提交时间: 2022-12-04 12:05:34
class Solution {
private StringBuilder removeInvalidClosing(CharSequence string, char open, char close) {
StringBuilder sb = new StringBuilder();
int balance = 0;
for (int i = 0; i < string.length(); i++) {
char c = string.charAt(i);
if (c == open) {
balance++;
} if (c == close) {
if (balance == 0) continue;
balance--;
}
sb.append(c);
}
return sb;
}
public String minRemoveToMakeValid(String s) {
StringBuilder result = removeInvalidClosing(s, '(', ')');
result = removeInvalidClosing(result.reverse(), ')', '(');
return result.reverse().toString();
}
}
java 解法, 执行用时: 16 ms, 内存消耗: 41.9 MB, 提交时间: 2022-12-04 12:05:18
class Solution {
public String minRemoveToMakeValid(String s) {
// Parse 1: Remove all invalid ")"
StringBuilder sb = new StringBuilder();
int openSeen = 0;
int balance = 0;
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (c == '(') {
openSeen++;
balance++;
} if (c == ')') {
if (balance == 0) continue;
balance--;
}
sb.append(c);
}
// Parse 2: Remove the rightmost "("
StringBuilder result = new StringBuilder();
int openToKeep = openSeen - balance;
for (int i = 0; i < sb.length(); i++) {
char c = sb.charAt(i);
if (c == '(') {
openToKeep--;
if (openToKeep < 0) continue;
}
result.append(c);
}
return result.toString();
}
}
python3 解法, 执行用时: 100 ms, 内存消耗: 17.4 MB, 提交时间: 2022-12-04 12:04:59
class Solution:
def minRemoveToMakeValid(self, s: str) -> str:
# Parse 1: Remove all invalid ")"
first_parse_chars = []
balance = 0
open_seen = 0
for c in s:
if c == "(":
balance += 1
open_seen += 1
if c == ")":
if balance == 0:
continue
balance -= 1
first_parse_chars.append(c)
# Parse 2: Remove the rightmost "("
result = []
open_to_keep = open_seen - balance
for c in first_parse_chars:
if c == "(":
open_to_keep -= 1
if open_to_keep < 0:
continue
result.append(c)
return "".join(result)
python3 解法, 执行用时: 108 ms, 内存消耗: 17.3 MB, 提交时间: 2022-12-04 12:04:29
class Solution:
def minRemoveToMakeValid(self, s: str) -> str:
def delete_invalid_closing(string, open_symbol, close_symbol):
sb = []
balance = 0
for c in string:
if c == open_symbol:
balance += 1
if c == close_symbol:
if balance == 0:
continue
balance -= 1
sb.append(c)
return "".join(sb)
# Note that s[::-1] gets the reverse of s.
s = delete_invalid_closing(s, "(", ")")
print(s)
s = delete_invalid_closing(s[::-1], ")", "(")
print(s)
return s[::-1]
python3 解法, 执行用时: 108 ms, 内存消耗: 17 MB, 提交时间: 2022-12-04 12:04:08
class Solution:
def minRemoveToMakeValid(self, s: str) -> str:
indexes_to_remove = set()
stack = []
for i, c in enumerate(s):
if c not in "()":
continue
if c == "(":
stack.append(i)
elif not stack:
indexes_to_remove.add(i)
else:
stack.pop()
indexes_to_remove = indexes_to_remove.union(set(stack))
string_builder = []
for i, c in enumerate(s):
if i not in indexes_to_remove:
string_builder.append(c)
return "".join(string_builder)