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

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) {

  StringBuilder response = new StringBuilder(input.length());

  char temp;

  for (int i = 0; i < input.length(); i++) {

     char next = input.charAt(i);

     if (temp != next) {

       temp = next;

       response.append(temp);

     }

  }

  return response.toString();

}

Answer 2

为什么不尝试使用正则表达式呢？就像这样：

public static void main(String[] args) {
    String str = "aabbaabbcccaaa";
    System.out.println(str.replaceAll("(.)\\1+","$1"));
}

输出：

ababca

编辑：
为了将来的参考，这种方法被证明是非常慢的。我使用 JMH 对它进行了基准测试，对于短字符串，它比非正则表达式解决方案慢大约 4 倍，并且对于较长（约 10k 个字符）的字符串只会变得更糟。