Thursday, January 12, 2012

String reverse algorithm

I went for a java technical interview recently and they told me to write simple java method to get the reverse of a given string object. I used java's 'StringBuilder' class and it provides 'reverse()' method. I guess, I am correct. They smiled and went one step ahead. They told me to do the same thing without using any java providing function and write my own function to reverse the string. I wrote that as well. Finally they told me to write it using the recursive algorithm. I was little stuck and they moved to next question. 

I came home and though for a algorithm to reverse the string. I came up with this solution. 

We can get the character array from the given string and characters can be swapped in the following manner.



public String reverseStr(String s) {
    char arr[] = reverseStr(0, s.toCharArray());
    return new String(arr);
}
private char[] reverseStr(int charIndex, char[] arr) {

    if (charIndex > arr.length - (charIndex+1)) {
      return arr;
    }
    char temp = arr[charIndex];
    arr[charIndex] = arr[arr.length - (charIndex+1)];
    arr[arr.length - (charIndex+1)] = temp;
  
    charIndex++;
  
    return reverseStr(charIndex, arr);
}
My implementation may not be the best way of doing this. I just wanted to find an algorithm for this.

2 comments:

  1. This question has already been answered multiple times, like for example in http://codemonkeyism.com/java-interview-questions-write-a-string-reverser-and-use-recursion/

    ReplyDelete
  2. Indeed this is one of those frequently asked java interview question, but knowing it without StringBuffer is tricky, it gets even more tricky when they asked to reverse string using iteration and recursion :)

    ReplyDelete

Share

Widgets