2 Ways to check If String is Palindrome in Java? Recursion and Loop

A String is said to be Palindrome if it is equal to itself in reverse order. You can use this logic to check if String is Palindrome or not. There are two common ways to find if a given String is Palindrome or not in Java, first by using for loop, also known as iterative algorithm and second by using recursion, also known as recursive algorithm. The crux of this problem lies in how do you reverse String in Java? because once you have the String in reverse order, problem reduced to just comparing itself with the reversed String. If both are equal then given String is Palindrome otherwise it's not. Also whether your solution is iterative or recursive will also determine by implementing this logic. If you reverse String using for loop then it become an iterative solution and if you reverse String using recursion then it become a recursive solution. In general, recursive solution are short, readable and more intuitive but subject to StackOverFlowError and that's why not advised to be used in production system. You should always be using iterative solution in production, unless your programming language supports tail recursion optimization e.g. Scala which eliminates risk of StackOverFlowError by internally converting a recursive solution to an iterative one. If you are doing this exercise as part of your Interview preparation then I suggest you to take a look at Cracking the Coding Interview: 150 Programming Questions and Solutions, as title says it contains 150 good questions based upon different topics e.g. String, array, linked list, binary tree, networking etc. A good book for preparing both Java and C++ interview.

Solution 1 : How to check if String is Palindrome using Recursion

Easiest way to find if a given String is Palindrome or not is by writing a recursive function to reverse the String first and then comparing given String with the reversed String, if both are equal then given String is palindrome. This logic is coded in our static utility method isPalindrome(String input) method. This method calls another method called reverse(String str), which is responsible for reversing given String using recursion. This method take out the last character and passed the rest of the String to the reverse() method itself,  when a method calls itself is called recursion. A recursive function needs a based case to terminate recursion and produce result. In this program, base case is empty String, if String is empty just return itself and don't call the method. We are also using substring() method from java.lang.String class to reduce the String in every call so that our solution reaches to base case after every call. If you remember the structure is quite similar to our earlier solution of problem how to find if a number is Palindrome in Java. Only thing different there was the logic to reverse numbers.

Solution 2 : How to check if String is Palindrome using Iteration

In our second solution we will try to solve this problem by using for loop. If you use any loop e.g. for, while or do..while then your solution is known as iterative solution. This solution uses extra space in form of StringBuilder which may or may not be allowed sometime. You can check with your interviewer whether you can use StringBuffer to reverse String in Java or not. He may not allow directly using reverse() method but he may allow it for String concatenation. The logic of this solution is coded in method checkPalindrome(String text). This method first create reversed String by iterating over String in reverse order e.g. starting from last index and going towards first index. You can easily do this in a for loop because it allows you to control index. It's actually quite similar to how you loop over array because String is a character array and you can get character array from String by calling toCharArray() method. Once you reverse the given String, its all about check if two Strings are equal to each other using equals() method, if it returns true then String is Palindrome.

Java Program to check if String is Palindrome Or Not

Here is our complete Java solution to problem of check if given String is Palindrome or not. This example program contains two methods, isPalindrome() and checkPalindrom(), first method check if String is Palindrome using loop while second method checks if String is Palindrome using recursion. We also have JUnit tests written to unit test our solution. I have two test methods testPalindromeRecursive() and testPalindrome(), first one tests our recursive solution and second one tests our iterative algorithm. You can see input there, "madam" is a Palindrome and our solution should return true for it. The line assertTrue(isPalindrome("madam")); does exactly same thing, it checks whether isPalindrome() method returns true for "madam" or not. 

import static org.junit.Assert.*;

import org.junit.Test;

/**
 * Java program to check if given String is palindrome or not.
 *
 * @author WINDOWS 8
 */

public class PalindromeChecker {

    /*
     * This method check if a given String is palindrome or not using recursion
     */
    public static boolean isPalindrome(String input) {
        if (input == null) {
            return false;
        }
        String reversed = reverse(input);

        return input.equals(reversed);
    }

    public static String reverse(String str) {
        if (str == null) {
            return null;
        }

        if (str.length() <= 1) {
            return str;
        }

        return reverse(str.substring(1)) + str.charAt(0);
    }
   
    /*
     * Iterative algorithm to check if given String is palindrome or not
     */
    public static boolean checkPalindrome(String text){
       
        StringBuilder sb = new StringBuilder(text);
        char[] contents = text.toCharArray();
       
        for(int i = text.length() -1; i>=0 ; i--){
            sb.append(contents[i]);
        }
       
        String reversed = sb.toString();
       
        return text.equals(reversed);
    }
   
    @Test
    public void testPalindromeRecursive(){
        assertTrue(isPalindrome("madam"));
        assertFalse(isPalindrome("programming"));
        assertTrue(isPalindrome(""));
        assertTrue(isPalindrome("AIA"));
    }
   
    @Test
    public void testPalindrome(){
        assertFalse(isPalindrome("wonder"));
        assertFalse(isPalindrome("cat"));
        assertTrue(isPalindrome("aaa"));
        assertTrue(isPalindrome("BOB"));
    }
}

Output
All test passes

That's all about how to check if String is Palindrome in Java. You have learned both iterative and recursive algorithms to verify whether String is Palindrome or not. If you are asked to write code about this problem, you first write code to check if String is palindrome using for loop, this will prompt Interviewer to ask you again to write same code using recursion and that time you write your solution using recursion. This will help you to drive the interview according to your plan and you will score more brownie points, just make sure that you don't rush for solution but spend some time thinking about it.

If you like this coding interview question and looking for some more coding problems for practice, you can check out some of programming questions from this blog :

• How to check if two String are Anagram or not? [solution]
• How to check if array contains a number in Java? [solution]
• Write a program to find missing number in integer array of 1 to 100? [solution]
• How do you reverse array in place in Java? [solution]
• How to check duplicate elements from Array in Java? [solution]
• How to remove duplicates from array in Java? [solution]
• Write a program to find top two numbers from an integer array? [solution]
• How to find maximum and minimum number in unsorted array? [solution]
• How to find all pairs on integer array whose sum is equal to given number? [solution]
• How to sort an array in place using QuickSort algorithm? [solution]
• How do you remove duplicates from array in place? [solution]

Recommended books to Prepare for Coding Interviews

If you are preparing for programming job interviews to find a software developer position then you must prepare for coding problems. Following books will help you to better prepare for your software engineering interview :

• Coding Puzzles: Thinking in code By codingtmd (check here)
• Programming Interviews Exposed: Secrets to Landing Your Next Job (check here)
• Cracking the Coding Interview: 150 Programming Questions and Solutions (check here)