Minimum Remove to Make Valid Parentheses
这题最难的地方是先想通这个minimum的意义是啥. 想一下,如果一个string可以选择性的删除某些括号, 不删除某些括号然后变成Valid Parentheses, 那么说明这些不需要删除的根本不是invalid. 所以其实就是问, 怎么删除多余的括号能让Valid Parentheses.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 |
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(); } } |