Reverse a String in Java
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&lt;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 &gt;= 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 &gt;= 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                           =&gt; 4473870 (hot 19.74881ms)
String Reverse Surrogate Aware           =&gt; 4473870 (hot 22.73488ms)
String Reverse B                         =&gt; 4473870 (hot 25.16192ms)
String Reverse StringBuilder             =&gt; 4473870 (hot 31.60709ms)
String Reverse StringBuilder NoNullCheck =&gt; 4473870 (hot 31.72952ms)
String Reverse Orig                      =&gt; 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 &gt;= 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 &lt; array.length; i++) {
        if (Character.isHighSurrogate(array[i]) &amp;&amp; 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 &gt;= 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.