Which variants string reverse are better?

Question

I'm wondering to know which program variant are better runtime?
Both variants looks easy to implement. But what are better to use and in which cases?

String reverse:

public static String reverse(String s)
{
    String rev = "";
    for (int i = s.length() - 1; i >= 0; i--)
        rev += s.charAt(i);
    return rev;
}

StringBuilder reverse:

public static String reverse(String s)
{
    StringBuilder rev = new StringBuilder();
    for (int i = s.length() - 1; i >= 0; i--)
        rev.append(s.charAt(i));
    return rev.toString();
}

How often do you need to do this? How much difference to the business will it make if you choose one option over the other? Until you can answer these questions, you don't have much basis to make a decision. All you can say is the second is more efficient than the first, *if* you have a string longer than 1 character. — Peter Lawrey, Apr 14 '13 at 08:52
Second snippet better it use `linear time`. First use `quadratic time`. — catch23, Apr 17 '13 at 16:13

score 6 · Accepted Answer · edited May 23 '17 at 11:57

in your two cases :i prefer the second one

because the compiler will convert the first one from :

rev += s.charAt(i);

to :

(new StringBuilder()).append(rev).append(s.charAt(i)).toString();

But , see the worst case scenario :

public class Main
{
    public static void main(String[] args)
    {
        long now = System.currentTimeMillis();
        slow();
        System.out.println("slow elapsed " + (System.currentTimeMillis() - now) + " ms");

        now = System.currentTimeMillis();
        fast();
        System.out.println("fast elapsed " + (System.currentTimeMillis() - now) + " ms");
    }

    private static void fast()
    {
        StringBuilder s = new StringBuilder();
        for(int i=0;i<100000;i++)
            s.append("*");      
    }

    private static void slow()
    {
        String s = "";
        for(int i=0;i<100000;i++)
            s+="*";
    }
}

the output will be :

slow elapsed 173 ms
fast elapsed 1 ms

+1 for pointing compiler conversion and providing time testing code (I'd +2 if I could! :) — acdcjunior, Apr 14 '13 at 08:24

score 5 · Answer 2 · answered Apr 14 '13 at 07:52

5

Neither is really great considering you can just do:

new StringBuilder(str).reverse().toString();

If you had to use one of the above though, then pick the StringBuilder reverse - with the first one you could well send the GC through the roof creating and disposing of as many string objects as you have characters.

answered Apr 14 '13 at 07:52

Michael Berry

70,193
21
157
216

3

Using StringBuilder.reverse() is different: it considers surrogate pairs as a single character, whereas both above snippets don't. So if surrogate pairs must be considered as a single char, using StringBuilder.reverse() is a good idea. Otherwise, if the performance is the main concern, it's probably slower than the second snippet. – JB Nizet Apr 14 '13 at 07:57

score 0 · Answer 3 · answered Apr 14 '13 at 08:10

String class in java is immutable and can't change in his life, and concatenation of two string create new String and return, but StringBuilder is a mutable sequence of characters that can change characters of string in memory, and using StringBuilder should be better.
as another solution, you can convert string to char array and reverse array and finally convert to String

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

for more information see javadoc: StringBuilder , String
and look StringBuilder class source codes to understand want is really happen on appending a character

score 0 · Answer 4 · answered Apr 17 '13 at 16:18

Some interesting details.
We can write a recursive function to reverse a string and don't use any loops. Use the String method substring():

public static String reverse(String s) {
   int N = s.length();
   if (N <= 1) return s;
   String a = s.substring(0, N/2);
   String b = s.substring(N/2, N);
   return reverse(b) + reverse(a);
}

How efficient is this method?
This method has a linearithmic running time.

Which variants string reverse are better?

4 Answers4