Monday, January 30, 2012

How to reverse String in Java using Iteration and Recursion

How to reverse string in java is popular core java interview question and asked on all levels from junior to senior java programming job. since Java has rich API most java programmer answer this question by using StringBuffer reverse() method which easily reverses an String in Java and its right way if you are programming in Java but most interview doesn't stop there and they ask interviewee to reverse String in Java without using StringBuffer or they will ask you to write an iterative reverse function which reverses string in Java. In this tutorial we will see how to reverse string in both iterative and recursive fashion. This example will help you to prepare better for using recursion in java which is often a weak area of Java programmer and exposed during a programming interview.

Reverse String in Java using Iteration and Recursion

How to reverse Java String using Iteration and Recursionif you are from C background and new to Java then you get surprise that java Strings are not character array instead they are object and Strings in Java are not null terminated but still you can use your C skill to write iterative reverse function for string by getting character array by calling String.toCharArray() and getting length of String by calling String.length(). Now if you succeed in writing String reverse function, an iterative version without using StringBuffer reverse than they finally ask you to write a recursive one. Since recursion is a tricky concept and not many Java developer think recursive as compared to C++ dudes, you may see many of Java programmer stuck here by doing doodling around subString, indexOf etc. So its better to prepare in advance. here I have given example of reversing string using StringBuffer, iterative version of String reversal and reversing string in Java using recursion. As I said recursive solution is always tricky to come up you need to found a suitable base case and than repetitive call recursive method with each call reducing length of argument. anyway mine way is just one way of reversing string using recursion, there are many solution out there. so don’t forget to try out yourself.

String Reverse Example using Iteration and Recursion in Java

Here is code example String reverse using  iterative and recursive function written in Java. Recursive solution is just for demonstrative and education purpose, don’t use recursive solution in production code as it may result in StackOverFlowError if String to be reversed is very long String or if you have any bug in your reverse function, anyway its good test to make yourself comfortable with recursive functions in java.

import java.io.FileNotFoundException;
import java.io.IOException;

/**
*
*@author Javin
/
public class StringReverseExample {

    public static void main(String args[]) throws FileNotFoundException, IOException {

        //original string
        String str = "Sony is going to introduce Internet TV soon";
        System.out.println("Original String: " + str);

        //reversed string using Stringbuffer
        String reverseStr = new StringBuffer(str).reverse().toString();
        System.out.println("Reverse String in Java using StringBuffer: " + reverseStr);

        //iterative method to reverse String in Java
        reverseStr = reverse(str);
        System.out.println("Reverse String in Java using Iteration: " + reverseStr);

        //recursive method to reverse String in Java
        reverseStr = reverseRecursively(str);
        System.out.println("Reverse String in Java using Recursion: " + reverseStr);

    }

    public static String reverse(String str) {
        StringBuilder strBuilder = new StringBuilder();
        char[] strChars = str.toCharArray();

        for (int i = strChars.length - 1; i >= 0; i--) {
            strBuilder.append(strChars[i]);
        }

        return strBuilder.toString();
    }

    public static String reverseRecursively(String str) {

        //base case to handle one char string and empty string
        if (str.length() < 2) {
            return str;
        }

        return reverseRecursively(str.substring(1)) + str.charAt(0);

    }
}


That’s all on how to reverse String in Java using Recursion, Iteration and without using StringBuffer. This is one of my favorite interview question and I mostly ask to write recursive solution just to know whether programmer has ability to comprehend recursive problem or not.

Here are few more Java interview questions you may like.

18 comments :

Chandraprakash Sarathe said...

Nice One - One more operation is Reversing the words of Palindrome Sentences.

String str = "India is Great becuase Great is India";

public String reverseWords(String str) {
String arr[]=str.split(" ");
StringBuilder stb=new StringBuilder();
for(int i=arr.length-1;i>=0;i--)
stb.append(arr[i]+" ");
return stb.toString();
}

Chandraprakash Sarathe
---------------------------
http://javaved.blogspot.com/

Javin @ spring interview questions answers said...

@Chandraprakash, indeed reversing words on String is also good interview question and can be asked in conjunction with reversing string using recursion. I see you have also good blog keep it up. you may also like core java interview questions and answers asked in Finance domain

Bappi said...

reversing string in java using loop is better than reversing string using recursion. code example of reverse string for loop looks much simpler and easy to understand than code example of recursive reversal of string. Another disadvantage of using recursion for reversing string is chance of StackOverFlowError. Also using loop is optimized way of reversing string in Java.

Jackson said...

Hi, I am looking answer for question on String, "How to reverse word in a String in Java", Can you guys please help with code example and explanation ? I have one more question regarding implementing wrapping of String. I have fixed size of String which may vary from one android device to another and I want to write my own String wrap function which takes Screen width and wrap String accordingly.

Dheeraj said...

I was looking for simple Java program to reverse String in Java when I find this great tutorial. This tutorial not only explains how to reverse String in Java with simple example of recursion and for loop but also explains logic behind it. Thanks for your Java program, you are helping programmers and developers in big way.

Anonymous said...

Can you please format this Java program for string reversal so that we can see the keyword in different color. I really like this Program to reverse String in Java and want to use in my site with attribution link, is it ok?

Zhesing said...

I was looking for a Java program to reverse String in Java without using StringBuffer reverse function when I come across this article. Its wonderful, Thanks for showing us two ways to reverse String in Java including tough one e.g. recursion. no matter how much I practice, it's always hard to reverse String using Recursion. I love to that using StringBuffer reverse() method if I am allowed to do so.

abhi said...

in the recursive function i think it will be nice to have a null check before we do str.length()

jtsiros said...

Be careful of the recursion function never returning. In this case when the recursion function is called, it will continuously go in a loop and won't terminate. You probably want some checks in there or else I'd say you failed that interview question ;)

Anonymous said...

Writing Java program to reverse a String without using reverse function or using recursion is just too popular and every body knows how to do that. There is no point asking this question in Interviews as you will get standard answers explained here.

Anonymous said...

For fun, here's an optimization to your recursive method.. even though Java doesn't currently support tail-call optimization.

public static String reverseRecursively(String str) {
     //base case to handle one char string and empty string
     if (str.length() < 2) {
          return str;
     }

     //tail-call optimization
     return reverseRecursively(str, "");
}

public static String reverseRecursively(String str, String reverseStr) {
     if (str.length() < 1) {
          return reverseStr;
     }
     StringBuilder strBuilder = new StringBuilder();
     strBuilder.append(str.charAt(0));
     strBuilder.append(reverseStr);
     return reverseRecursively(str.substring(1), strBuilder.toString());
}

Michael Surbey said...

For fun, another example:

// iterative method to reverse String in Java
public static String reverse(String str) {
char[] c = str.toCharArray();

for (int i=0; i < str.length(); i++)
for (int j=c.length-1; j > i; j--) {
char temp = c[j];
c[j] = c[j-1];
c[j-1] = temp;
}

return new String(c);
}

Additionally, a cool Java trick is if there is only one expression or statement after a control structure... Curly brackets aren't necessary!

Dipeshv said...

Below will help to avoid inner loops
public class StringRecursion {

/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
String str="abcdefghi";
int strMaxIndex=str.length()-1;
char[] c=str.toCharArray();
char temp;
System.out.print("String Before:"+c.toString());

for(int i=0;i<=strMaxIndex;i++)
{

if(i>=strMaxIndex-i)
{
break;
}
temp=c[i];
c[i]=c[strMaxIndex-i];
c[strMaxIndex-i]=temp;
}
System.out.print("\nString After:"+c.toString());


}

}

vinaykumar said...

Another way, run only half the size of chars o(n/2)

public static String getReversedString(String str)
{
char[] chars = str.toCharArray();

for(int i = 0 ; i < chars.length/2; i ++)
{
char temp1 = chars[i];

chars[i]= chars[chars.length-i-1];
chars[chars.length-i-1]= temp1;

}

return new String(chars);
}

Meera Menon said...

reverseRecursively - does that work ?

Anonymous said...

Can i get the code of java to print the string "please test" to "test please" and also for the input string also. Please reply this answer on niksy@ymail.com

mrityunjay said...

String str = "India is Great becuase Great is India";

public String reverseWords(String str) {
String arr[]=str.split(" ");
StringBuilder stb=new StringBuilder();
for(int i=arr.length-1;i>=0;i--)
stb.append(arr[i]+" ");
return stb.toString();
}

Anonymous said...

@vinaykumar +1 , that solution was first that came up to my mind

Post a Comment