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

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 一次。您可以通过使用 StringBuilder 对响应 String 进行优化，并且可能为了可读性而稍微简化循环(不需要 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();
}