从字符串中删除相邻的重复项

Question

我需要编写一个函数来接收字符串并删除相邻的重复项。

示例：

输入 -> “aabbaabbcccaaa”

输出 -> “ababca”

我尝试按如下方式解决：

public String remdups(String input) {

    String response = "";

    char temp;

    int i, length = input.length();

    for(i = 0; i < length; i++) {

        temp = input.charAt(i);

        response += temp;

        while(i < length && input.charAt(i) == temp) i++;

    }

    return response;

}

但时间复杂度似乎没有达到预期，我该如何提高性能或者有什么更好的方法？我知道这是一个非常简单的问题，但我找不到改进的方法或其他方法来做到这一点。

Answer 1

对我来说，从复杂性的角度来看，您的代码看起来已经很好了。它只遍历字符串一次。您可以对响应进行优化，String使用 a StringBuilder，并且可能为了可读性而稍微简化循环（不需要 2 个嵌套循环，并且i从 2 个位置递增计数器可能会引入错误）。public String remdups(String input) {&nbsp; StringBuilder response = new StringBuilder(input.length());&nbsp; char temp;&nbsp; for (int i = 0; i < input.length(); i++) {&nbsp; &nbsp; &nbsp;char next = input.charAt(i);&nbsp; &nbsp; &nbsp;if (temp != next) {&nbsp; &nbsp; &nbsp; &nbsp;temp = next;&nbsp; &nbsp; &nbsp; &nbsp;response.append(temp);&nbsp; &nbsp; &nbsp;}&nbsp; }&nbsp; return response.toString();}

Answer 2

为什么不尝试使用正则表达式呢？就像这样：public&nbsp;static&nbsp;void&nbsp;main(String[]&nbsp;args)&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;String&nbsp;str&nbsp;=&nbsp;"aabbaabbcccaaa"; &nbsp;&nbsp;&nbsp;&nbsp;System.out.println(str.replaceAll("(.)\\1+","$1")); }输出：ababca编辑：为了将来的参考，这种方法被证明是非常慢的。我使用 JMH 对它进行了基准测试，对于短字符串，它比非正则表达式解决方案慢大约 4 倍，并且对于较长（约 10k 个字符）的字符串只会变得更糟。