2 Ways to check If String is Palindrome in Java? Recursion and Loop Example Tutorial (original) (raw)

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 an iterative algorithm, and second by using recursion, also known as a 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, the problem is reduced to just comparing itself with the reversed String. If both are equal then the 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 becomes an iterative solution and if you reverse String using recursion then it becomes a recursive solution. In general, recursive solutions are short, readable, and more intuitive but subject to StackOverFlowError and that's why not advised to be used in the production systems.

You should always be using iterative solutions in production unless your programming language supports tail recursion optimization e.g. Scala which eliminates the risk of StackOverFlowError by internally converting a recursive solution to an iterative one.

Btw, every programmer should know about basic data structures like an array, linked list, binary tree, hash table, and others. It helps you to write better code and also crack interviews, if you want to improve your algorithms skills then you can also join a comprehensive Data Structure and Algorithms course like Data Structures and Algorithms: Deep Dive Using Java on Udemy to fill the gaps in your understanding.

If you are doing this exercise as part of your Interview preparation then I suggest you take a look at Cracking the Coding Interview: 189 Programming Questions and Solutions, as the 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.

How to check if given String is Palindrome in Java

Without wasting any more of your time, here are both the recursive and iterative algorithms to check if the given String is a Palindrome in Java or not. You can use the solution you want but you must understand the pros and cons of each approach and should be able to pick the right solution depending upon circumstances like production vs test and others. Many interviewers test this decision-making ability of candidates during technical interviews.

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

The 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 the given String with the reversed String, if both are equal then the given String is a 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 takes 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 results. In this program, the 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 the base case after every call.

f you remember the structure is quite similar to our earlier solution of the problem of how to find if a number is a Palindrome in Java. The 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 creates reversed String by iterating over String in reverse order e.g. starting from last index and going towards the first index. You can easily do this in a for loop because it allows you to control the 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 - Example

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.

I have also written 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;

/**

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

Now, let's run the JUnit test to see they are passing or not", you can see both tests are gree which means our code is working fine.

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 the interviewer to ask you again to write some 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 a solution but spend some time thinking about it.