Reverse string в Java: учимся реверсировать строки разными способами

Можно ли стать хорошим программистом без знания алгоритмов? Весьма и весьма спорно. Да, вы сможете найти работу в наших аутсорс-компаниях, ведь в них на собеседованиях задают вопросы в большей степени по технологиям. Но будете ли вы хорошим специалистом, если ваши решения будут вовсю напичканы костылями? Если вы захотите перейти в более серьезную зарубежную компанию, столкнетесь с собеседованиями, ориентированными в первую очередь на алгоритмы. Так или иначе, стоит взять на вооружение самые базовые алгоритмы, ведь алгоритм — друг программиста. Сегодня мы затронем одну из таких тем и обсудим способы реверсирования строки. Тут все просто. Реверсирование строки — это получение строки задом наперёд. Например: JavaRush forever ->reverof hsuRavaJ Итак, как же можно перевернуть строку в Java?

1. StringBuilder/StringBuffer

Самый банальный и простой способ — использовать StringBuilder/StringBuffer:

public static String reverseString(String str) {
  return new StringBuilder(str).reverse().toString();
}

Лучшее решение = самое простое. При вопросе о том, как перевернуть строку (reverse string в Java) это первое, что должно приходить в голову. Но мы ранее говорили об алгоритмах, не правда ли? Давайте взглянем на решения не “из коробки”.

2. Решение с массивом

public static String reverseString(String str) {
  char[] array = str.toCharArray();
  String result = "";
  for (int i = array.length - 1; i >= 0; i--) {
     result = result + array[i];
  }
  return result;
}

Переводим нашу строку в массив с помощью метода toCharArray. Пробежимся циклом for по данному массиву с его конца, попутно добавляя символы в результирующую строку.

3. Решение с charAt

public static String reverseString(String str) {
  String result = "";
  for (int i = 0; i < str.length(); i++) {
     result = str.charAt(i) + result;
  }
  return result;
}

В данном случаем нам даже строку на массив разбивать не придется, так как каждый символ мы вытягиваем с помощью метода класса String — charAt (цикл for, опять же, у нас обратный, что позволяет нам брать символы последовательно задом-наперёд).

4. Решение со Stack

Класс Stack давно никто не использует, и он считается устаревшим, но тем не менее, для ознакомления будет полезно взглянуть на решение с его использованием:

public static String reverseString(String str) {
  Stack<Character> stack = new Stack<>();
  String result = "";
  for (Character character : str.toCharArray()) {
     stack.add(character);
  }
  while (!stack.isEmpty()) {
     result = result + stack.pop();
  }
  return result;
}

Здесь опять же используем toCharArray для разбивки строки на массив и кладем всё это в наш Stack с дженерик типом Character. Далее начинаем брать элементы с верхушки стека. Из-за особенностей стека как структуры LIFO — Last In First Out (первый вошел, последний вышел), элементы будут браться задом-наперед и следствие сохранятся в результирующую строку.

5. Решение рекурсией

Почти каждую задачу на алгоритмы можно решить с помощью рекурсии. И тут мы тоже не обойдемся без нее. Или даже без них. Ведь сегодня мы рассмотрим даже не один способ решения рекурсией, а несколько.

• способ первый

  
  public static String reverseString(String str) {
    String rightStr;
    String leftStr;
    int length = str.length();
  
    if (length <= 1) {
       return str;
    }
   
    leftStr = str.substring(0, length / 2);
    rightStr = str.substring(length / 2, length);
   
    return reverseString(rightStr) + reverseString(leftStr);
  }
  

  Переменные rightStr и leftStr мы используем для разбивки пришедшей строки на две равные части. Далее с помощью такой разбивки мы дробим строку на наименьшие делимые части (1 символ). После рекурсия начинает сворачиваться, возвращая символы в противоположном порядке (те, что были справа — поставили слева; те, что были слева — вправо)

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

• способ второй

  Здесь нам понадобится дополнительный аргумент в методе — index.

  При запуске этого метода он задается длиной строки -1:

  
  String str = "JavaRush forever";
  System.out.println(reverseString(str, str.length()-1));
  

  И сам метод:

  
  public static String reverseString(String str, int index) {
    if(index == 0){
       return str.charAt(0) + "";
    }
   
    char letter = str.charAt(index);
    return letter + reverseString(str, index-1);
  }
  

  Индекс у нас служит индикатором того, какой элемент строки мы будем использовать сейчас (а элементы мы будем использовать с конца).

  Поэтому задаём условия выхода при достижении индексом первого элемента.

Складываем значения полученного с помощью индекса letter с результатом предыдущего выполнения метода и возвращаем результат.

• способ третий

  
  public static String reverseString(String str) {
    if (str.length() <= 1) {
       return str;
    }
    return reverseString(str.substring(1)) + str.charAt(0);
  }
  

  Данный способ по сути является самым простым из рекурсивных. А как мы помним, простое = лучшее.

  Во время каждого запуска мы задаем ту же строку, но без первого элемента. При достижении условия выхода (когда у нас останется один символ) рекурсия начинает сворачиваться, и к каждому последующему результату будет добавляться предыдущий неиспользованный символ.

6. При помощи XOR

XOR — логическая побитовая операция. В случае двух переменных результат выполнения операции истинен тогда и только тогда, когда один из аргументов истинен, а другой — ложен. Подробнее о побитовых операциях можно почитать в этой статье. Следующее решение будет опираться на то, что:

(A XOR B) XOR B = A
(A XOR B) XOR A = B

Как будет выглядеть метод:

public static String reverseString(String str) {
  char[] arr = str.toCharArray();
  int low = 0;
  int high = arr.length - 1;
  String result = "";
  while (low < high) {
     arr[low] = (char) (arr[low] ^ arr[high]);
     arr[high] = (char) (arr[low] ^ arr[high]);
     arr[low] = (char) (arr[low] ^ arr[high]);
     low++;
     high--;
  }
  for (int i = 0; i < arr.length; i++) {
     result = result + arr[i];
  }
  return result;
}

Давайте разбираться с тем, что тут происходит. Мы создаём массив из входящей строки. Создаём две переменные, low и high, хранящие индексы для прохода по массиву. Соответственно, один будет двигаться с начала в конец — ему задаём значение 0, второй — с конца в начало, ему задаем arr.length - 1. Заходим в цикл, который будет воспроизводиться, пока индекс high больше, чем low. Тут начинает происходить самое интересное — использование исключающего ИЛИ. Давайте разберем на примере x и y. Предположим, что arr[high] = 'x'; Двоичный код у него будет 1 1 1 1 0 0 0 В это время arr[high] = 'n'; Двоичный код — 1 1 0 1 1 1 0 Что мы будем иметь в XOR операциях в цикле:

1. arr[low] = (char) (arr[low] ^ arr[high]);

   
   arr[low] = 1 1 0 1 1 1 0
   arr[high] =1 1 1 1 0 0 0
   arr[low] = 0 0 1 0 1 1 0
   

2. arr[high] = (char) (arr[low] ^ arr[high]);

   
   arr[low] =  0 0 1 0 1 1 0
   arr[high] = 1 1 1 1 0 0 0
   arr[high] = 1 1 0 1 1 1 0
   

3. arr[low] = (char) (arr[low] ^ arr[high]);

   
   arr[low] =  0 0 1 0 1 1 0
   arr[high] = 1 1 0 1 1 1 0
   arr[low] =  1 1 1 1 0 0 0
   

В итоге благодаря этим операциям мы поменяли местами значения двух ячеек массива. arr[high] отдален от конца массива на столько же элементов, на сколько arr[low] отдален от начала. Поэтому мы просто меняем элементы с этими индексами местами. Например, при первом выполнении в предложении "JavaRush forever" J и r поменяются местами, при втором — a и e и т. д. Если у нас нечетное количество символов, то при достижении элемента, который находится посередине, нас выбросит из цикла (т.к. средний элемент менять и не нужно). Если чётное — нас выбросит после обработки всех элементов. Ну а после мы заходим в обычный цикл и строим строку из элементов массива.