通过删除连续的 k 个字符直到无法删除来缩小字符串"abbcccbfgh"

Question

通过删除连续的k个字符来收缩字符串"abbccccbfgh"，直到无法删除为止。例如，对于k=3，上述字符串的输出将为"阿富汗"。请注意，K和字符串都是动态的，即由用户提供。

我写了下面的程序，但无法完成。请帮忙。

public class Test {
public static void main(String[] args) {
String str = "abbcccbfgh";
int k = 3;
String result = removeConsecutive(str, k);
System.out.print("result is " + result);
}
private static String removeConsecutive(String str, int k) {
String str1 = str + "";
String res = "";
int len = str.length();
char c1 = 0, c2 = 0;
int count = 0;
for (int i = 0; i < len - 1; i++) {
c1 = str.charAt(i);
c2 = str.charAt(i + 1);
if (c1 == c2) {
count++;
} else {
res = res + String.valueOf(c1);
count = 0;
}
if (count == k-1) {
//remove String
}
}
return res;
}

Answer 1

我建议使用regex:

int l = 0;
do {
l = str.length();
str = str.replaceAll("(.)\1{" + n + "}", "");
} while (l != str.length());

n=k-1

(.)\1｛2｝表示后面跟有n个相同字符的任何字符\1表示与组#1 中相同的字符

Answer 2

是否可以进行递归？

public class Test {
public static void main(String[] args) {
String str = "abbcccbfgh";
int k = 3;
String result = removeConsecutive(str, k);
System.out.print("result is " + result);
}
private static String removeConsecutive(String str, int k) {
String ret = str;
int len = str.length();
int count = 0;
char c1 = 0 ;
char c2 = 0;
char last = 0 ;
for (int i = 0; i < ret.length()-1; i++) {
last = c1 ;
c1 = str.charAt(i);
c2 = str.charAt(i + 1);
if (c1 == c2 ) {
if( count > 0 ) {
if( last == c1 ) {
count ++ ;
}
else {
count = 0;
}
}
else {
count++;
}
} else {
count = 0;
}

if (count == k-1) {

int start = ((i+1) - k) + 1 ;
String one = str.substring(0, start) ;
String two = str.substring(start+k);
String new1 = one + two ;
//recursion
ret = removeConsecutive(new1, k) ;
count = 0;
}
}
return ret;
}
}

Answer 3

您可以使用堆栈来完成。对于字符串中的每个字符ch，将其推送到堆栈中，如果有3个连续的相同字符，则将它们全部弹出。最后，将堆栈转换为字符串。您可以使用一个特殊的堆栈来记住每个元素的出现次数，从而稍微改进程序。

import java.util.ArrayList;
import java.util.List;
import java.util.function.Function;
public class Reduce implements Function<String, String> {
private final int k;
public Reduce(final int k) {
if (k <= 0) {
throw new IllegalArgumentException();
}
this.k = k;
}
@Override
public String apply(final String s) {
Stack<Character> stack = new Stack<>();
for (Character ch : s.toCharArray()) {
stack.push(ch);
if (stack.topCount() == k) {
stack.pop();
}
}
return stack.toString();
}
public static void main(String[] args) {
Reduce reduce = new Reduce(3);
System.out.println(reduce.apply("abbcccbfgh"));
}
private static class Stack<T> {
private class Node {
private T value;
private int count;
Node(T value) {
this.value = value;
this.count = 1;
}
}
private List<Node> nodes = new ArrayList<>();
public void push(T value) {
if (nodes.isEmpty() || !top().value.equals(value)) {
nodes.add(new Node(value));
} else {
top().count++;
}
}
public int topCount() {
return top().count;
}
public void pop() {
nodes.remove(nodes.size()-1);
}
private Node top() {
return nodes.get(nodes.size()-1);
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
nodes.forEach(n->{
for (int i = 0; i < n.count; i++) {
sb.append(n.value);
}
});
return sb.toString();
}
}
}