Reverse string in Java: learning to reverse strings in different ways

Is it possible to become a good programmer without knowing algorithms? Very, very controversial. Yes, you can find a job in our outsourcing companies, because during interviews they ask questions mostly about technology. But will you be a good specialist if your decisions are full of crutches? If you want to move to a more serious foreign company, you will encounter interviews that are primarily focused on algorithms. One way or another, it’s worth adopting the most basic algorithms, because an algorithm is a programmer’s friend . Today we will touch on one of these topics and discuss ways to reverse a string. Everything is simple here. Reversing a string is getting the string backwards. For example: JavaRush forever ->reverof hsuRavaJ So, how can you reverse a string in Java?

1. StringBuilder/StringBuffer

The most common and simple way is to use StringBuilder/StringBuffer :

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

Best solution = simplest. When asked how to reverse a string in Java, this is the first thing that should come to mind. But we talked about algorithms earlier, didn't we? Let's take a look at solutions that aren't out of the box.

2. Array solution

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;
}

We convert our string into an array using the toCharArray method . Let's run a for loop through this array from its end, adding characters to the resulting string along the way.

3. Solution with charAt

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

In this case, we don’t even have to split the string into an array, since we extract each character using the String class method - charAt (the for loop, again, is reverse, which allows us to take characters sequentially backwards).

4. Solution with Stack

The Stack class has not been used for a long time, and it is considered obsolete, but nevertheless, for reference, it will be useful to look at a solution using it:

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;
}

Here again we use toCharArray to split the string into an array and put it all in our Stack with a generic type Character . Next, we start taking elements from the top of the stack. Due to the nature of the stack as a LIFO structure - L ast I n F irst O ut (first in, last out), elements will be taken backwards and the result will be stored in the resulting row.

5. Solution by recursion

Almost every algorithm problem can be solved using recursion. And here we also cannot do without her. Or even without them. After all, today we will consider not just one method of solving recursion, but several.

• method one

  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);
  }

  We use the rightStr and leftStr variables to split the incoming string into two equal parts. Next, using this split, we split the string into the smallest divisible parts (1 character). Afterwards, the recursion begins to collapse, returning the characters in the opposite order (those that were on the right were placed on the left; those that were on the left were placed on the right)

  We must not forget that each recursion is a multiple call to a method, and as a result, a considerable expenditure of resources. Well, if we are talking about recursion with an unattainable exit condition, then this is the path to infinity and to StackOverflowError.

• method two

  Here we need an additional argument in the method - index.

  When this method is run, it is given a string length of -1:

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

  And the method itself:

  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);
  }

  Our index serves as an indicator of which row element we will use now (and we will use the elements from the end).

  Therefore, we set exit conditions when the index reaches the first element.

We add the values ​​obtained using the letter index with the result of the previous execution of the method and return the result.

• method three

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

  This method is essentially the simplest of the recursive ones. And as we remember, simple = best.

  During each run, we specify the same string, but without the first element. When the exit condition is reached (when we have one character left), the recursion begins to collapse, and the previous unused character will be added to each subsequent result.

6. Using XOR

XOR is a logical bitwise operation. In the case of two variables, the result of an operation is true if and only if one of the arguments is true and the other is false. You can read more about bitwise operations in this article . The next solution will rely on the fact that:

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

What the method will look like:

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;
}

Let's figure out what's going on here. We create an array from the incoming string. We create two variables, low and high , that store indexes for traversing the array. Accordingly, one will move from beginning to end - we give it the value 0, the second - from end to beginning, we set it arr.length - 1 . We enter a loop that will play as long as the index high is greater than low . This is where the fun stuff starts to happen - the use of exclusive OR. Let's look at x and y as an example . Suppose arr[high] = 'x'; Its binary code will be 1 1 1 1 0 0 0 At this time arr[high] = 'n'; Binary code - 1 1 0 1 1 1 0 What we will have in XOR operations in a loop:

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

As a result, thanks to these operations, we swapped the values ​​of two array cells. arr[high] is as many elements from the end of the array as arr[low] is from the beginning. Therefore, we simply swap the elements with these indices. For example, on the first execution in the sentence “JavaRush forever” J and r will be swapped, on the second - a and e , etc. If we have an odd number of characters, then when we reach the element that is in the middle, we will be thrown out of the loop (i.e. There is no need to change the middle element). If it’s even, we’ll be thrown out after processing all the elements. Well, after that we go into a regular loop and build a string from the array elements.