How to Reverse a String
As stated in the How to Interview a Java Programmer post one question that you can ask which doesn't require a computer to answer is "Write a reverseString method". I asked this question to my co-workers and got quite a few different responses. Then another co-worker put the responses together and benchmarked them. Below is the results.
Kevin responded with how to reverse a String in Ruby:
"Hello World".reverse
"Hello World".split(//).reverse.to_s
reversed = []
"Hello World".split(//).each{|c| reversed.insert(0,c)}
reversed.to_s
My initial approaches are below:
String s = "Hello World";
________________________________________________________
String returnS;
for (int i = s.length() - 1; i >= 0; i--) {
returnS += s.substring(i, 1);
}
return returnS;
_____________________________________________________
StringBuffer buffer = new StringBuffer(s.length());
for (int i = s.length() - 1; i >= 0; i--) {
buffer.append(s.substring(i, 1));
}
return buffer.toString();
_______________________________________________________
StringBuffer buffer = new StringBuffer(s);
buffer.reverse();
return buffer.toString();
______________________________________________________________
StringCharacterIterator iterator = new StringCharacterIterator(s);
char[] chars = new char[s.length()];
int i = 0;
for(char c = iter.last(); c != CharacterIterator.DONE; c = iter.previous()) {
chars[i++] = c;
}
return new String(chars);
______________________________________________________________
int length = s.length(), last = length - 1;
char[] chars = s.toCharArray();
for ( int i = 0; i < length/2; i++ ) {
char c = chars[i];
chars[i] = chars[last - i];
chars[last - i] = c;
}
return new String(chars);
Tim had another variant of the array based approach:
String s = "Hello World";
int length = s.length();
char[] chars = new char[length];
for (int i = 0; i < length; i++){
chars[length - i] = s.charAt(i);
}
return new String(chars);
Josh responded with a interesting file based approach:
CharArrayWriter caw = new CharArrayWriter(s.length());And Eric showed how to use the Apache StringUtils and ArrayUtils:
for(int i = s.length()-1; i >=0; i--){
caw.write((int)s.charAt(i));
}
char[] letters = caw.toCharArray();
DataOutputStream dos = new DataOutputStream(new FileOutputStream(new File("helloWorld")));
try{
for(int i = 0; i < letters.length; i++){
dos.write((int)letters[i]);
}
}
catch(Exception ex){
// if this failed, we can't read it back
throw new EndOfTheUniverseException();
}
finally{
dos.close();
}
DataInputStream dis = new DataInputStream(new FileInputStream(new File("helloWorld")));
caw = new CharArrayWriter();
try{
caw.write((int)dis.readChar());
}
catch(Exception ex){/* looks like we're done */}
finally{ dis.close(); }
String returnS = new String(caw.toCharArray());
return returnS;
return StringUtils.reverse(s);
________________________________________________
char[] chars = s.toCharArray();
ArrayUtils.reverse(chars);
return new String(chars);
Last but not least here is the benchmarks from 2 Strings and the code to exercise the methods:
import static java.lang.System.currentTimeMillis;
import static java.lang.System.out;import java.lang.reflect.Method;
import java.text.CharacterIterator;
import java.text.StringCharacterIterator;
import org.apache.commons.lang.ArrayUtils;
import org.apache.commons.lang.StringUtils;
public class ReverseStringTest {
public static final void main(String... args) throws Exception {
new ReverseStringTest().runTest();
}
private void runTest() throws Exception {
String s = "Hello World, what would you like to do this fine evening?";
for(int i = 1; i < 10; i++) {
Method method = getClass().getMethod("method"+i, new Class[] {String.class});
out.println("method to be ran = " + method + "with output = " + method.invoke(this, new Object[] {s}));
long begin = currentTimeMillis();
for(int j = 0; j < 1000000; j++) {
method.invoke(this, new Object[] {s});
}
long end = currentTimeMillis();
out.println("time taken to run = " + (end - begin) + " milliseconds");
} }
public final String method1(String s) {
String returnS = "";
for (int i = s.length() - 1; i >= 0; i--) {
returnS += s.substring(i, i + 1);
}
return returnS;}
public final String method2(String s) {
StringBuffer buffer = new StringBuffer(s.length());
for (int i = s.length() - 1; i >= 0; i--) {
buffer.append(s.substring(i, i + 1));
}
return buffer.toString();}
public final String method3(String s) {
StringBuffer buffer = new StringBuffer(s);
buffer.reverse();
return buffer.toString();}
public final String method4(String s) {
StringCharacterIterator iterator = new StringCharacterIterator(s);
char[] chars = new char[s.length()];
int i = 0;
for(char c = iterator.last(); c != CharacterIterator.DONE; c = iterator.previous()) {
chars[i++] = c;
}
return new String(chars);}
public final String method5(String s) {
int length = s.length(), last = length - 1;
char[] chars = s.toCharArray();
for ( int i = 0; i < length/2; i++ ) {
char c = chars[i];
chars[i] = chars[last - i];
chars[last - i] = c;}
return new String(chars);}
public final String method6(String s) {
return new StringBuilder(s).reverse().toString();}
public final String method7(String s) {
StringBuilder buffer = new StringBuilder(s.length());
for (int i = s.length() - 1; i >= 0; i--) {
buffer.append(s.substring(i, i + 1));}
return buffer.toString();}
public final String method8(String s) {
return StringUtils.reverse(s);}
public final String method9(String s) {
char[] chars = s.toCharArray();
ArrayUtils.reverse(chars);
return new String(chars);}}
Posted at 10:21PM Jun 25, 2006 by Aaron in Java |