Удалить соседние дубликаты из строки - PullRequest
Новая
       30

Удалить соседние дубликаты из строки

3 голосов
/ 28 сентября 2019

Мне нужно написать функцию, которая получает строку и удаляет соседние дубликаты.
Пример:
Ввод -> "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;
}

Но, похоже, чтосложность во времени не такая, как ожидалось, как я могу улучшить производительность или что было бы лучше?Я знаю, что это действительно простая проблема, но я не могу найти способ улучшить или другой способ сделать это.

Ответы [ 2 ]

3 голосов
/ 29 сентября 2019

Мне ваш код уже выглядит хорошо с точки зрения сложности.Он проходит через Струну только один раз.Оптимизация, которую вы могли бы выполнить, заключается в ответе String с использованием 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();
}
2 голосов
/ 28 сентября 2019

Почему бы не попробовать что-нибудь с регулярным выражением?Например: 

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

Вывод: 

ababca

Редактировать:
Для дальнейшего использования этот подход оказывается крайне медленным.Я сравнил его с JMH, и он примерно в 4 раза медленнее, чем решение без регулярных выражений для коротких строк, и ухудшается только для более длинных (~ 10 тыс. Символов) строк.

...