Reversing a string in Java is fairly straightforward. We iterate from the end to the beginning of the original string, constructing the reverse string one character at a time. A java implementation could look as follows:
/**
* Reverse the specified string.
* @param string
* @return
*/
public static String stringReverse(String string) {
String reversed = "";
for(int i = string.length() - 1; i >= 0; i--) {
reversed += string.charAt(i);
}
return reversed;
}
However, this involves creating a new string so therefore the space complexity is O(n) and thus isn’t an in-place algorithm. The following algorithm swaps beginning and end elements in order to accomplish reversing the string with O(1) space complexity.
Algorithm string_reverse( S )
Input: S, a string of size n
Output: S', the reversed string
begin
for(i=0 to n, j=n-1 to 0) {
c = S[i];
S[i] = S[j];
S[j] = c;
}
return S;
end
Since there is no setChar(i, x) method defined on the String class in Java, it seems necessary to define a char[] Array in order to implement string_reverse. However, this brings us back to increasing the space complexity to O(n). Therefore, it seems a char[] array would be necessary as the input, rather than a String, in a Java implementation of reversing a string in O(1)-time.
/**
* Reverse the specified string, in-place.
* @param string
* @return
*/
public static char[] stringReverseInPlace(char[] string) {
for(int i = 0, j = string.length - 1; i < string.length / 2; i++, j--) {
char c = string[i];
string[i] = string[j];
string[j] = c;
}
return string;
}