Recently I attended a job interview, in which they asked me to write an algorithm to reverse a String - "Hello World" to "dlroW olleH".
It sounded simple and I wrote something like below.
private String reverse(String str) {
char[] charArray=str.toCharArray();
String reverse = "";
for (int i = charArray.length-1,j=0; i >= 0 ; i --,j++) {
reverse +=charArray[i];
}
return reverse;
}
Then I was asked, how I will write if I need to reverse using recursion. Well, I couldn't write it at that point, I said, I will do it something like this
function reverse(String rev) {
if (size of rev == 1) {
return rev;
}
return (lastChar + reverse(substr(first to last but one)))
}
It appeared simple, but made me to think there is something wrong in my approach. I felt that guilt until I reached home. After going home I couldn't resist writing a small program for reversing a String using multiple approaches.
Below are the scenarios I tried :
- Reversing a String using recursion & substring
- Reversing manually char by char, but concatenating to a String
- Directly using reverse() function of java StringBuilder
- Reversing manually char by char, but appending to a StringBuilder
- Reversing manually char by char, inserting chars to a new char array
Exactly like what I did in the interview.
/**
* Reverses the string using recursion of substrings
*
* @param str - string to be reversed
* @return reversed string
*/
private static String reverse1(String str) {
if (str.length() <= 0) {
return str;
}
int len = str.length();
return str.substring(len-1,len)+(reverse1(str.substring(0,len-1)));
}
Again, exactly like what I did in the interview.
/**
* Reverses the string char by char and concatinating to a new String
*
* @param str - String to be reversed
* @return reversed string
*/
private static String reverse2(String str) {
char[] charArray=str.toCharArray();
String reverse = "";
for (int i = charArray.length-1,j=0; i >= 0 ; i --,j++) {
reverse +=charArray[i];
}
return reverse;
}
Here, as you can see I am directly calling reverse() function of StringBuilder instead of manually reversing it.
/**
* More simple way in java, using StringBuilder's reverse method
*
* @param str - string to be reversed
* @return - reversed string
*/
private static String reverse3(String str) {
return new StringBuilder(str).reverse().toString();
}
Here instead of concatenating to a String, I am appending the reversed characters to a StringBuilder
/**
* Reverses the string char by char, but appends to a StringBuilder
*
* @param str - String to be reversed
* @return reversed string
*/
private static String reverse4(String str) {
char[] charArray=str.toCharArray();
StringBuilder reverse=new StringBuilder();
for (int i = charArray.length-1; i >= 0 ; i --) {
reverse.append(charArray[i]);
}
return reverse.toString();
}
Here instead of concatenating to a String or appending to a StringBuilder, I am inserting the reversed chars into new char array.
/**
* Reverses the string char by char and building reverse char array
*
* @param str - String to be reversed
* @return reversed string
*/
private static String reverse5(String str) {
char[] charArray=str.toCharArray();
char[] reverse = new char[charArray.length];
for (int i=charArray.length-1,j=0; i >= 0;) {
reverse[j++] = charArray[i--];
}
return new String(reverse);
}
Called all methods one after the other from Reverse.main() & noting the elapsed time after each call. I used a original string with length > 2000. Something like below.
"Lorem ipsum dolor sit amet, consectetur adipisicing elit, sed do eiusmod tempor incididunt ut labore et dolore magna aliqua. Ut enim ad minim veniam, quis nostrud exercitation ullamco laboris nisi ut aliquip ex ea commodo consequat. Duis aute irure dolor in reprehenderit in voluptate velit esse cillum dolore eu fugiat nulla pariatur. Excepteur sint occaecat cupidatat non proident, sunt in culpa qui officia deserunt mollit anim id est laborum. Sed ut perspiciatis unde omnis iste natus error sit voluptatem accusantium doloremque laudantium, totam rem aperiam, eaque ipsa quae ab illo inventore veritatis et quasi architecto beatae vitae dicta sunt explicabo. Nemo enim ipsam voluptatem quia voluptas sit aspernatur aut odit aut fugit, sed quia consequuntur magni dolores eos qui ratione voluptatem sequi nesciunt. Neque porro quisquam est, qui dolorem ipsum quia dolor sit amet, consectetur, adipisci velit, sed quia non numquam eius modi tempora incidunt ut labore et dolore magnam aliquam quaerat voluptatem. Ut enim ad minima veniam, quis nostrum exercitationem ullam corporis suscipit laboriosam, nisi ut aliquid ex ea commodi consequatur? Quis autem vel eum iure reprehenderit qui in ea voluptate velit esse quam nihil molestiae consequatur, vel illum qui dolorem eum fugiat quo voluptas nulla pariatur? But I must explain to you how all this mistaken idea of denouncing pleasure and praising pain was born and I will give you a complete account of the system, and expound the actual teachings of the great explorer of the truth, the master-builder of human happiness. No one rejects, dislikes, or avoids pleasure itself, because it is pleasure, but because those who do not know how to pursue pleasure rationally encounter consequences that are extremely painful. Nor again is there anyone who loves or pursues or desires to obtain pain of itself, because it is pain, but because occasionally circumstances occur in which toil and pain can procure him some great pleasure. To take a trivial example, which of us ever undertakes laborious physical exercise, except to obtain some advantage from it? But who has any right to find fault with a man who chooses to enjoy a pleasure that has no annoying consequences, or one who avoids a pain that produces no resultant pleasure?"
Results :
Reverse 1 (Recursive substring) : 22 milli seconds
Reverse 2 (Manual Reverse by concating to a new String) : 25 milli seconds
Reverse 3 (StringBuilder.reverse()) : 1 milli seconds
Reverse 4 (Manual with StringBuilder.append()) : 3 milli seconds
Reverse 5 (Manual by creating new char array) : 1 milli seconds
Conclusion :
If you are using Java as programming language, Java's StringBuilder.reverse() is the simplest & fastest method for reversing a String. Sometimes, it is better to use java's built-in util methods than writing our own complex methods just to show that we know recursion or We want to do it in our way. However, if you want to do this from first principles, 5th method gives the best results - O(N).
References
I liked this article written by Joel Spolsky in his blog - The Guerrilla Guide to Interviewing (version 3.0). If you are interviewing Software Engineers for your company or attending interviews, it is a good read.