Saturday, 29 June 2013

Algorithm: Reverse a string

Problem

Reverse a string in the most efficient way possible. For example an input of "abc123" will result in the output "321cba".

Analysis

This is a very common interview question, it tests whether a candidate understands how string concatenation and immutability works. A simple algorithm that does the job loops through each character and constructs a string in reverse order.

function reverse (text)
define result ← ""
foreach character c in text
result ← c + result
return result

The above algorithm is not very efficient though. This is because strings are immutable which means they cannot be modified after they are created. The algorithm creates a new string every iteration which takes worst case $O(n)$, making the algorithm $O(n^2)$.

The string can be reversed in $O(n)$ time with a couple of different methods: using StringBuilder to construct the string as above, or by converting the string to a character array and back.

Code

View on GitHub

Char array

String reverse(String text) {
char[] charArray = text.toCharArray();
int start = -1;
int end = charArray.length;
while (++start < --end) {
char temp = charArray[start];
charArray[start] = charArray[end];
charArray[end] = temp;
}
return String.valueOf(charArray);
}

StringBuilder

String reverse(String text) {
StringBuilder sb = new StringBuilder();
for (int i = text.length() - 1; i >= 0; i--) {
sb.append(text.charAt(i));
}
return sb.toString();
}

or

public static String reverse(String text) {
return new StringBuilder(text).reverse().toString();
}