题目
给你一个由 '('、')' 和小写字母组成的字符串 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)" 也是一个可行答案。
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/minimum-remove-to-make-valid-parentheses
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
题解
- 和判断有效括号类似。
- 维护一个左括号栈(栈中存元素索引)和无效括号位的数组。遇到左括号,压栈,置无效。遇到右括号,若左括号栈为空,则置无效;否则,弹出左括号栈顶元素,并置该位为有效。
最后,用StringBuilder把有效位字符连接到一起返回。
代码
import java.util.Stack;
class Solution {
public String minRemoveToMakeValid(String s) {
Stack<Integer> stack = new Stack<>();
boolean[] notVaild = new boolean[s.length()];
StringBuilder newStr = new StringBuilder();
for(int i=0;i<s.length();++i){
char c = s.charAt(i);
if(c=='('){
stack.push(i);
notVaild[i]=true;
}else if(c==')'){
if(stack.empty()){
notVaild[i]=true;
}else{
notVaild[stack.pop()]=false;
}
}
}
for(int i=0;i<s.length();++i){
if(!notVaild[i]){
newStr.append(s.charAt(i));
}
}
return newStr.toString();
}
}