正在寻找一个性能更好的Java字符串替换解决方案

Question

给定一个只能有字母的字符串输入。如果存在AB、CD、BA、DC的组合，则应通过删除这些出现的字符串并返回结果字符串来转换字符串。示例：

1. 输入：ABDCC->输出：C
2. 输入：CABABD->CABD->CD->输出：空字符串我提出了一个使用字符串替换函数的解决方案，但正在寻找一个更高性能或替代的解决方案。有什么想法吗

public String transformString(String s) {
HashSet<String> stringsToRemove = new HashSet();
stringsToRemove.add("AB");
stringsToRemove.add("BA");
stringsToRemove.add("CD");
stringsToRemove.add("DC");

int prevLength = -1;
while (prevLength != s.length()) {
prevLength = s.length();
for (String d : stringsToRemove) {
s = s.replace(d, "");
}
}
return s;
}

Answer 1

从括号匹配中获取策略并使用堆栈。让您开始的解决方案草图：

Stack<Character> stack = new Stack<>();
for (char c : s.toCharArray()) {
if (stack.empty()) {
stack.push(c);
}
else {
char t = stack.peek();
if (/* t and c match, such as 'A' and 'B' */) {
stack.pop();
}
else {
stack.push(c);
}
}
}
// Return a string based on what's left in the stack.

显然，只有当"；匹配"；没有边缘案例，例如user3386109在他们的评论中提到的案例。

这只经过输入两次(一次在循环中，一次展开堆栈以构建输出(，输入大小的线性时间也是如此。

Answer 2

一种基本的递归方法(未优化(：

public static Set<String> replacements = Set.of("AB", "BA", "CD", "DC");
public String minLenStr(String a, String b){
if (a.length() <= b.length()){
return a;
} else {
return b;
}
}
public String reduceStringUtil(String str, String curMin){
System.out.println("reduceString(%s, %s)".formatted(str, curMin));
if (str.length() == 0 || curMin.length() == 0){
return "";
}
for (String rep : replacements){
String newStr = str.replace(rep, "");
if (!str.equals(newStr)){
String newStr2 = reduceStringUtil(newStr, curMin);
curMin = minLenStr(newStr, newStr2);
}
}
return curMin;
}
public String reduceString(String str){
return reduceStringUtil(str, str);
}

Answer 3

我尝试了自己的基于StringBuilder的实现，并将其与这里已经发布的递归和堆栈实现进行了比较。

public String removeAll(String original, Set<String> removals) {
StringBuilder result = new StringBuilder(original);
int resultLength = result.length();
int oldLength = 0;
do {
for(String remove : removals) {
int position = 0;
while(position >= 0) {
position = result.indexOf(remove, position);
if(position >= 0) {
result.delete(position, position + remove.length());
}
}
}
oldLength = resultLength;
resultLength = result.length();
} while ((resultLength > 0) && (resultLength < oldLength));
return result.toString();
}

我用1000个长度为100的字符串对它进行了测试，这些字符串是从'A'、'B'、'C'和'D'中随机创建的(当然，在一次比较运行中，所有算法都有相同的1000个字符串(。

• 我在上面发布的算法花费了你原来算法的50%左右的时间
• 基于递归的算法非常依赖于输入的长度(试图用100个长度为1000的字符串进行测试，但不得不终止它，因为我不想等待几分钟才能得到这个实现的结果(，对于这里描述的配置，它所花费的时间约为原始实现的7500%
• 基于堆栈的算法可能是错误的-对于问题中指定的两个测试用例，它得到了相同的结果，但对于我的随机输入，它没有给出与原始算法相同的结果。此外，它所花费的时间非常依赖于输入，从原始算法时间的50%到200%，但平均而言，它所花的时间比原始算法更长。(为了优化，我用不同步的Deque替换了同步的Stack，并尝试了该接口的几种实现，ArrayDeque似乎是该算法中速度最快的。(

也许我在实现基于堆栈的算法时犯了一些错误，因为@Welbog没有给出完整的实现。我在这里发布我的实现进行比较，如果你发现错误，请给出反馈：

private static final Character[] EMPTY_ARRAY_STRING = new Character[0];
public String removeAll(String original, Set<String> remove) {
Deque<Character> stack = new ArrayDeque<>();
for (char c : original.toCharArray()) {
if (stack.isEmpty()) {
stack.push(c);
}
else {
final char t = stack.peek();
boolean matches = false;
for(Iterator<String> iterator = remove.iterator(); iterator.hasNext() && !matches; ) {
String rem = iterator.next();
matches = (t == rem.charAt(0) && c == rem.charAt(1));
}
if (matches) {
stack.pop();
}
else {
stack.push(c);
}
}
}
return Arrays.toString(stack.toArray(EMPTY_ARRAY_STRING));
}