Reverse a String in Java

Question

Here is the code for the CString class that I created.

public class CString {

    public String reverse(String s) {
        char[] array = new char[s.length()];
        array = s.toCharArray();
        for(int i=0; i<array.length/2; i++) {
            char tmp = array[i];
            array[i] = array[array.length-1-i];
            array[array.length-1-i] = tmp;
        }
        return charArrayToString(array);
    }

    public String charArrayToString(char[] array) {
        StringBuffer sb = new StringBuffer();
        sb.append(array);
        return sb.toString();
    }
}

Is there any bug in the code? Are there more efficient ways to reverse a string?

Answer 1

Reversing a string, accurately and efficiently.

You are doing it accurately, yes. But, not very efficiently (although there are worse ways to do things).

NOTE:: Palacsint is right that you are not handling null input and surrogate-pairs in the input data. Your solution is not completely accurate. Consider this answer a discussion of the efficiency only.... though I have also updated this answer to include a solution which deals with surrogate pairs efficiently

To understand the efficiency side of things, you have to understand Java String internals.

• Strings are immutable, cannot be changed.
• Java is relatively slow at allocating/cleaning memory, try to avoid it.
• Java can 'inline' method calls and make methods really fast.

So, the best way to make Java efficient is to create/use as little memory as possible, and still end up with a new String (instead of changing an existing string).

Your code has 1 string already, you are creating another string. You cannot avoid that.

What you can avoid though is what happens in between.

Your 'In Between'

What you are doing in between is a bit messy, and wasteful:

    char[] array = new char[s.length()];
    array = s.toCharArray();

You create a new array, then you throw it away, and replace it with the s.toCharArray()... why?

Could be just:

    char[] array = s.toCharArray();

Also, you have a loop that swaps the chars... this is implemented like:

for(int i=0; i<array.length/2; i++) {

This could be faster if you did it backwards ( could be - depending on which Java you use).

for (int i = array.length / 2; i >= 0; i--) {

This way it only has to do the array.length / 2 one time (though, as I say, some Java implementations will perhaps compile it to work out for you).

Finally, the charArrayToString() is serious overkill....

Converting to a StringBuilder then to a String is a waste of time/resources...

return charArrayToString(array);

can be

return new String(array);

EDIT: Also, as has been mentioned by Richard Miskin... and I assumed you were already using a StringBuilder .... StringBuilder is much more efficient in a single-thread situation than StringBuffer. Unless you have good reason, you always should use StringBuilder.

Efficient in-between ....

public String reverse(String s) {
    char[] array = s.toCharArray();
    char tmp;
    for(int i = (array.length - 1) / 2; i >= 0; i--) {
        tmp = array[i];
        array[i] = array[array.length-1-i];
        array[array.length-1-i] = tmp;
    }
    return new String(array);
}

Edit: a different way:

Here are some performance numbers...

String Reverse                           => 4473870 (hot 19.74881ms)
String Reverse Surrogate Aware           => 4473870 (hot 22.73488ms)
String Reverse B                         => 4473870 (hot 25.16192ms)
String Reverse StringBuilder             => 4473870 (hot 31.60709ms)
String Reverse StringBuilder NoNullCheck => 4473870 (hot 31.72952ms)
String Reverse Orig                      => 4473870 (hot 36.83827ms)

For each of those 'hot' runs, I am reversing the order of 479829 words (linux.words) (and there are 4473870 characters in the data excluding newlines).

• the code I suggested above as the 'efficient in-between' does it in 20 milliseconds

• based on the discussion about null and Surrogate Pairs, the following code does this 'right', and runs in 23 milliseconds:

  public String reverse(final String s) {
      if (s == null) {
          return null;
      }
      final char[] array = s.toCharArray();
      char tmp;
      for(int i=array.length/2; i >= 0; i--) {
          tmp = array[i];
          array[i] = array[array.length-1-i];
          array[array.length-1-i] = tmp;
      }
      //surrogate pairs will have been swapped.
      //identify, and un-swap them.
      for (int i = 1; i < array.length; i++) {
          if (Character.isHighSurrogate(array[i]) && Character.isLowSurrogate(array[i - 1])) {
              tmp = array[i];
              array[i] = array[i - 1];
              array[i - 1] = tmp;
          }
      }
      return new String(array);
  }
  

• The following code does it in 25 milliseconds

  public String reverse(String s) {
      char[] array = new char[s.length()];
      for(int i=array.length - 1, j = 0; i >= 0; i--, j++) {
          array[i] = s.charAt(j);
      }
      return new String(array);
  }
  

• @palacsint's recommendation does it in 31 milliseconds:

  public static String reverse(final String str) {
      if (str == null) {
          return null;
      }
      return new StringBuilder(str).reverse().toString();
  } 
  

• @palacsint's recommendation (without the null-check) does it in 31 milliseconds:

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

• Your code does it in 37milliseconds.

If you look at the code, my code creates three objects (char[] and new String() (which creates char[] as well))

The s.charAt() code also creates three objects, but has a lot of calls to String.charAt().

The @palacsint recommendation creates 4 objects (StringBuffer, StringBuffer's internal char[], String, and String's internal char[]);

That is true with and without the null-check.

Your code creates 5 objects (6 if you count the first array which is likely to be compiled out...) : (char[] array, new StringBuffer, StringBuffer's char[], String, and String's char[])

My guess is that there is a close correlation between our times simply because it takes 5ms to create 480,000 objects on the heap, plus some overhead of actual work.

Answer 2

Learn from the existing implementations, they usually have solutions to corner cases and common pitfalls. For example, Apache Commons Lang StringUtils also has a reverse function. Its implementation is quite simple:

public static String reverse(final String str) {
    if (str == null) {
        return null;
    }
    return new StringBuilder(str).reverse().toString();
} 

It uses StringBuilder.reverse whose javadoc mentions some special cases:

If there are any surrogate pairs included in the sequence, these are treated as single characters for the reverse operation. Thus, the order of the high-low surrogates is never reversed.

Here are a few tests:

@Test
public void testCstring() {
    assertEquals("\uD800\uDC00", CString.reverse("\uD800\uDC00")); // fails
    assertEquals("\uD800\uDC00", CString.reverse("\uDC00\uD800")); // OK
}

@Test
public void testStringUtils() throws Exception {
    assertEquals("\uD800\uDC00", StringUtils.reverse("\uD800\uDC00"));
    assertEquals("\uD800\uDC00", StringUtils.reverse("\uDC00\uD800"));
}

I don't know too much about these surrogates but you should check it and handle them in your code. I suppose the JDK's implementation is more reliable and it's not coincidence that the handle them in the way they mention in the javadoc.

There is a good question (with great answers) about surrogates on Stack Overflow: What is a surrogate pair in Java?

(See also: Effective Java, 2nd edition, Item 47: Know and use the libraries)

Answer 3

The code appears to be functionally correct, although you could simply choose to use a StringBuffer.reverse(). There is some discussion of this here.

If you do need to roll your own reversing method, you can avoid using StringBuffer/StringBuilder at all and simply do new String(array) instead.

As a general point, if you're not dealing with multithreaded code you should probably use StringBuilder in preference to StringBuffer.

Answer 4

You can use Java 8 lambda functions to reverse a string without mutating or using any local variables. This code will illustrate the reverse function:

public static void reverse(String myString) {
    return myString
                .chars()
                .mapToObj(c -> String.valueOf((char) c))
                .reduce("", (sb, str) -> str + sb);     
}

This code gets you the integer stream from the String object:

myString.chars()

Once you have the integer stream you can transform the integers to characters using the map function:

mapToObj(c -> String.valueOf((char) c))

Then finally you can reduce your characters the way you want. Here I have prepended the characters to the final output string:

reduce("", (sb, str) -> str + sb);