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

The following does not deal with UTF-16 surrogate pairs.

public static String reverse(String orig)
{
    char[] s = orig.toCharArray();
    int n = s.length;
    int halfLength = n / 2;
    for (int i=0; i<halfLength; i++)
    {
        char temp = s[i];
        s[i] = s[n-1-i];
        s[n-1-i] = temp;
    }
    return new String(s);
}

Answer 2

If you do not want to use any built in function, you need to go back with the string to its component parts: an array of chars.

Now the question becomes what is the most efficient way to reverse an array? The answer to this question in practice also depends upon memory usage (for very large strings), but in theory efficiency in these cases is measured in array accesses.

The easiest way is to create a new array and fill it with the values you encounter while reverse iterating over the original array, and returning the new array. (Although with a temporary variable you could also do this without an additional array, as in Simon Nickersons answer).

In this way you access each element exactly once for an array with n elements. Thus giving an efficiency of O(n).

Answer 3

private static String reverse(String str) {
    int i = 0;
    int j = str.length()-1;
    char []c = str.toCharArray();
    while(i <= j){
        char t = str.charAt(i);
        c[i] = str.charAt(j);
        c[j]=t;
        i++;
        j--;
    }
    return new String(c);
}

Answer 4

Using multiple threads to swap the elements:

    final char[] strArray = str.toCharArray();

    IntStream.range(0, str.length() / 2).parallel().forEach(e -> {
        final char tmp = strArray[e];
        strArray[e] = strArray[str.length() - e - 1];
        strArray[str.length() - e - 1] = tmp;
    });
    return new String(strArray);

Answer 5

static String ReverseString(String input) {
    var len = input.Length - 1;
    int i = 0;
    char[] revString = new char[len+1];
    while (len >= 0) {
        revString[i] = input[len];
        len--; 
        i++;
    }
    return new string(revString);   
}

why can't we stick with the simplest loop and revere with character read and keep adding to the char array, I have come across with a whiteboard interview, where interviewer set restrictions on not to use StringBuilder and inbuilt functions.

Answer 6

char* rev(char* str)
    {
    int end= strlen(str)-1;
    int start = 0;

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

    ++start;
    --end;
    }

    return str;
}

=========================

Wondering how it works?

First operation:

x1 = x1 XOR x2

x1: 1   0   0
x2: 1   1   1
New x1: 0   1   1

Second operation

x2 = x2 XOR x1

x1: 0   1   1
x2: 1   1   1
New x2: 1   0   0
//Notice that X2 has become X1 now

Third operation:

x1 = x1 XOR x2
x1: 0   1   1
x2: 1   0   0
New x1: 1   1   1
//Notice that X1 became X2