Minimum Remove to Make Valid Parentheses
这题最难的地方是先想通这个minimum的意义是啥. 想一下,如果一个string可以选择性的删除某些括号, 不删除某些括号然后变成Valid Parentheses, 那么说明这些不需要删除的根本不是invalid. 所以其实就是问, 怎么删除多余的括号能让Valid Parentheses.
class Solution {
public String minRemoveToMakeValid(String s) {
Set<Integer> set = new HashSet<>();
Stack<Integer> st = new Stack<>();
for(int i = 0; i < s.length(); i++) {
if(s.charAt(i) == '(') {
st.push(i);
}
if(s.charAt(i) == ')') {
if(st.isEmpty()) {
set.add(i);
}
else {
st.pop();
}
}
}
while(!st.isEmpty()) {
set.add(st.pop());
}
StringBuilder sb = new StringBuilder();
for(int i = 0; i < s.length(); i++) {
if(set.contains(i))
continue;
sb.append(s.charAt(i));
}
return sb.toString();
}
}