What is the most efficient algorithm for reversing

Question

What is the most efficient way to reverse a string in Java? Should I use some sort of xor operator? The easy way would be to put all the chars in a stack and put them back into a string again but I doubt that's a very efficient way to do it.

And please do not tell me to use some built in function in Java. I am interested in learning how to do it not to use an efficient function but not knowing why it's efficient or how it's built up.

Answer 1

I'm not really sure by what you mean when you say you need an efficient algorithm.

The ways of reversing a string that I can think of are (they are all already mentioned in other answers):

1. Use a stack (your idea).

2. Create a new reversed String by adding characters one by one in reverse order from the original String to a blank String/StringBuilder/char[].

3. Exchange all characters in the first half of the String with its corresponding position in the last half (i.e. the ith character gets swapped with the (length-i-1)th character).

The thing is that all of them have the same runtime complexity: O(N). Thus it cannot really be argued that any one is any significantly better than the others for very large values of N (i.e. very large strings).

The third method does have one thing going for it, the other two require O(N) extra space (for the stack or the new String), while it can perform swaps in place. But Strings are immutable in Java so you need to perform swaps on a newly created StringBuilder/char[] anyway and thus end up needing O(N) extra space.

Answer 2

I think that if you REALLY don't have performance problem you should just go with the most readable solution which is:

StringUtils.reverse("Hello World");

Answer 3

You say you want to know the most efficient way and you don't want to know some standard built-in way of doing this. Then I say to you: RTSL (read the source, luke):

Check out the source code for AbstractStringBuilder#reverse, which gets called by StringBuilder#reverse. I bet it does some stuff that you would not have considered for a robust reverse operation.

Answer 4

You said you don't want to do it the easy way, but for those Googling you should use StringBuilder.reverse:

String reversed = new StringBuilder(s).reverse().toString();

If you need to implement it yourself, then iterate over the characters in reverse order and append them to a StringBuilder. You have to be careful if there are (or can be) surrogate pairs, as these should not be reversed. The method shown above does this for you automatically, which is why you should use it if possible.

Answer 5

I would simply do it this way without a use of any single util function. Just the String class is sufficient.

public class MyStringUtil {

    public static void main(String[] args) {
        String reversedString = reverse("StringToReverse");
        System.out.println("Reversed String : " + reversedString);
    }

    /**
     * Reverses the given string and returns reversed string
     * 
     * @param s Input String
     * @returns reversed string
     */
    private static String reverse(String s) {
        char[] charArray = s.toCharArray(); // Returns the String's internal character array copy
        int j = charArray.length - 1;
        for (int i = 0; charArray.length > 0 && i < j; i++, j--) {
            char ch = charArray[i];
            charArray[i] = charArray[j];
            charArray[j] = ch;
        }
        return charArray.toString();
    }
}

Check it. Cheers!!

Answer 6

public class ReverseInPlace {

  static char[]  str=null;

    public static void main(String s[]) {
      if(s.length==0)
        System.exit(-1);

       str=s[0].toCharArray();

       int begin=0;
       int end=str.length-1;

       System.out.print("Original string=");
       for(int i=0; i<str.length; i++){
         System.out.print(str[i]);
       }

       while(begin<end){
          str[begin]= (char) (str[begin]^str[end]);
          str[end]= (char)   (str[begin]^str[end]);
          str[begin]= (char) (str[end]^str[begin]);

          begin++;
          end--;       
       }

       System.out.print("\n" + "Reversed string=");
       for(int i=0; i<str.length; i++){
         System.out.print(str[i]);
       }

    }
}