Reversing a String in Java (In-Place)

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;
	}

Leave a Reply

Your email address will not be published. Required fields are marked *