JavaRush /Java блог /Java Developer /Reverse string в Java: учимся реверсировать строки разным...
Автор
John Selawsky
Senior Java-разработчик и преподаватель в LearningTree

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

Статья из группы Java Developer
Можно ли стать хорошим программистом без знания алгоритмов? Весьма и весьма спорно. Да, вы сможете найти работу в наших аутсорс-компаниях, ведь в них на собеседованиях задают вопросы в большей степени по технологиям. Reverse string в Java: учимся реверсировать строки разными способами - 1Но будете ли вы хорошим специалистом, если ваши решения будут вовсю напичканы костылями? Если вы захотите перейти в более серьезную зарубежную компанию, столкнетесь с собеседованиями, ориентированными в первую очередь на алгоритмы. Так или иначе, стоит взять на вооружение самые базовые алгоритмы, ведь алгоритм — друг программиста. Сегодня мы затронем одну из таких тем и обсудим способы реверсирования строки. Тут все просто. Реверсирование строки — это получение строки задом наперёд. Например: 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;
}
В данном случаем нам даже строку на массив разбивать не придется, так как каждый символ мы вытягиваем с помощью метода класса StringcharAt (цикл 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. Далее начинаем брать элементы с верхушки стека. Из-за особенностей стека как структуры LIFOLast 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 B Y
0 0 0
0 1 1
1 0 1
1 1 0
Подробнее о побитовых операциях можно почитать в этой статье. Следующее решение будет опираться на то, что:

(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 и т. д. Если у нас нечетное количество символов, то при достижении элемента, который находится посередине, нас выбросит из цикла (т.к. средний элемент менять и не нужно). Если чётное — нас выбросит после обработки всех элементов. Ну а после мы заходим в обычный цикл и строим строку из элементов массива.
Комментарии (22)
ЧТОБЫ ПОСМОТРЕТЬ ВСЕ КОММЕНТАРИИ ИЛИ ОСТАВИТЬ КОММЕНТАРИЙ,
ПЕРЕЙДИТЕ В ПОЛНУЮ ВЕРСИЮ
Роман Уровень 17
19 декабря 2023
А я так сделал. Всю "Война и мир" перевернул :)

 Path filePath = of("D:\WarAndPeace\WarAndPeace.txt");
 String source = File.readString(filePath);
 StringBuilder reverced = new StringBuilder();
 for(int x = source.length() - 1; x >= 0; x --) {
 reverced.append(source.charAt(x));
 }
 System.out.print(reverced);
} catch (OutOfMemoryError | IOException memoryError) {
return; }
31 марта 2022
Можно так: import org.apache.commons.lang3.*; StringUtils.reverse(str);
Dion Уровень 17
31 июля 2020
Как реализовать реверс строки, чтоб при этом позиции небуквенных символов не менялись? Пример: a1bcd efg!h -> d1cba hgf!e.
Pavel Kurashov Уровень 17 Expert
21 июня 2020
3. Решение с charAt Мне одному кажется что цикл здесь как раз прямой - от 0 до длины строки? Мы собираем строку в обратной последовательности. Путаница в определениях.
16 июня 2020
алгоритм с XOR, вместо

for (int i = 0; i < arr.length; i++) {
     result = result + arr[i];
  }
return result;
просто

return new String(arr);
Иван Ганжа Уровень 41
16 июня 2020
Есть задача в программировании, как поменять местами значение двух переменных без использование дополнительной. В последнем примере как раз этим и занимаются.
Nikolay Nickolskiy Уровень 27
16 июня 2020
Использовать в циклах String - это конечно дно днищенское.
Asad Vice Уровень 22
15 июня 2020
кто нибудь замерял по скорости и используемой памяти? Сравнительная таблица покажет предпочтительный вариант
AButrym Уровень 1
15 июня 2020
То, что Stack устарел, означает что вместо него рекомендуют использовать другой класс - https://docs.oracle.com/en/java/javase/11/docs/api/java.base/java/util/ArrayDeque.html с его методами push/pop