移除无效的括号
难度:
标签:
题目描述
代码结果
运行时间: 50 ms, 内存: 17.5 MB
/*
* 思路:
* 使用Java Stream API来简化代码:
* 1. 使用过滤器去掉多余的右括号 ')'
* 2. 使用过滤器去掉多余的左括号 '('。
*/
import java.util.stream.Collectors;
public class Solution {
public String minRemoveToMakeValid(String s) {
int open = 0;
StringBuilder sb = new StringBuilder();
// First pass: remove extra ')'
s.chars().forEach(c -> {
if (c == '(') open++;
if (c == ')') {
if (open == 0) return;
open--;
}
sb.append((char) c);
});
open = 0;
String result = sb.reverse().chars()
.filter(c -> {
if (c == ')') open++;
if (c == '(') {
if (open == 0) return false;
open--;
}
return true;
})
.mapToObj(c -> String.valueOf((char) c))
.collect(Collectors.joining());
return new StringBuilder(result).reverse().toString();
}
}
解释
方法:
此题解通过利用栈结构来跟踪并处理字符串中的括号。首先,将字符串转换为字符数组,以便能够修改特定索引的字符。遍历字符数组时,遇到'('时将其索引入栈,表示一个潜在的未匹配左括号。遇到')'时,检查栈是否为空:如果不为空,表示栈顶的'('可以与之匹配,于是将其出栈;如果为空,说明当前的')'无法匹配,将其位置上的字符设为空字符串。遍历完成后,栈中剩余的都是未能匹配的'('的索引,将这些位置上的字符同样设为空字符串。最后,将修改后的字符数组重新组合成字符串。
时间复杂度:
O(n)
空间复杂度:
O(n)
代码细节讲解
🦆
在处理无法匹配的')'时,直接将其设为空字符串,这是否意味着这个字符会在最终的字符串中完全消失?
▷🦆
如何确定所有未匹配的'('在栈中的索引,并确保它们在最后被正确地删除?
▷🦆
此算法是否考虑了输入字符串中只含有小写字母而没有任何括号的情况?如果是,算法是如何处理这种情况的?
▷