ref{:target=”_blank”}
使用stack,左括号下标入栈,右括号进行匹配,发现栈空,则对应的右括号非法,最后匹配结束后,stack内多余的左括号是非法的
C++ 代码
class Solution {
public:
string minRemoveToMakeValid(string s) {
int n = s.size();
vector<bool> valid(n, true);
stack<int> stk;
// 寻找非法的右括号下标
for(int i=0; i<n; ++i) {
char c = s[i];
if('(' == c) {
stk.push(i);
} else if(')' == c) {
if(stk.empty()) valid[i] = false;
else stk.pop();
}
}
// 寻找非法的左括号下标
while(stk.size()) {
valid[stk.top()] = false;
stk.pop();
}
// 计算答案
string res;
for(int i=0; i<n; ++i) {
if(valid[i])res += s[i];
}
return res;
}
};