Remove All Adjacent Duplicates in String II
给一个string, 只移除k次重复的substring.
这个题因为要多次移除, 还有merge的可能, 所以要用stack存一下前序, 我是用Pair先预处理了一下string, 把string换成词频格式, 然后再用stack. 其实也可以不用pair, 直接算.
|
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 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 |
class Solution { class Pair{ char a; int b; Pair(char a, int b){ this.a = a; this.b = b; } public String toString(){ return this.a +"|" + this.b; } } public String removeDuplicates(String s, int k) { List<Pair> pairs = new LinkedList<>(); for(int i = 0; i < s.length(); i++) { if(pairs.isEmpty() || pairs.get(pairs.size() - 1).a != s.charAt(i)){ Pair p = new Pair(s.charAt(i), 1); pairs.add(p); } else if(pairs.get(pairs.size() - 1).a == s.charAt(i)){ Pair p = new Pair(pairs.get(pairs.size() - 1).a, pairs.get(pairs.size() - 1).b + 1); pairs.remove(pairs.size() - 1); pairs.add(p); } } Stack<Pair> st = new Stack<>(); for(int i = 0; i < pairs.size(); i++){ if(st.isEmpty()){ st.push(pairs.get(i)); } else if(st.peek().a == pairs.get(i).a){ Pair p = st.pop(); p.b += pairs.get(i).b; st.push(p); }else{ st.push(pairs.get(i)); } if(!st.isEmpty()){ Pair p = st.pop(); if(p.b % k != 0){ p.b = p.b % k; st.push(p); } } } StringBuilder sb = new StringBuilder(); while(!st.isEmpty()){ Pair p = st.pop(); for(int i = 0; i < p.b; i++) { sb.insert(0, p.a); } } return sb.toString(); } } |