Sunday, September 24, 2023

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

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;

/**
 * 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

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. 

How to check if String is Palindrome in Java



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.

Recommended books and courses 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 and courses will help you to better prepare for your software engineering interview :

1. Best Coding interview Books for Programmers


If you like this coding interview question and looking for some more coding problems for practice, you can check out some of the 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]

Thanks for reading this article so far. If you find it useful then please share with your friends and colleagues. 

And lastly one question for you? Which one is your favorite Java coding exercise? Prime number, Fibonacci, Factorial or this one? 

11 comments :

Anonymous said...

3rd way: http://stackoverflow.com/questions/7569335/reverse-a-string-in-java

new StringBuilder(hi).reverse().toString()

Suan said...

Hi! Great article. :)

Here's an alternative solution (if you're interested):-

String a = "wooow";
int j = a.length() - 1;
for (int i = 0; i < a.length() / 2; i++) {
if (a.charAt(i) != a.charAt(j)) {
System.out.println("NOT PALINDROME!");
break;
}
j--;
}

It's a O(n) solution which is pretty cool. We use two pointers moving from the front and back of the String respectively. Once a mismatched char is found, we can safely say that the String is not a palindrome.

Cheer!

Unknown said...

Hey dear Paul nice article :)
I would like to explain me this line :
return reverse(str.substring(1)) + str.charAt(0);

javin paul said...

Hello @Hybrid Static, here we are extracting the first character and passing rest of the String to method itself (the recursive call). After that we are adding that first character at then end of what reverse() return. So if your string is "abcd" then str.substring(1) = bcd and str.charAt(0) = a.

When recursion will complete and things will start rolling back e.g. when input to reverse is empty then you will have something like this "" + "d" + "c" + "b" + "a", which will produce final output "dcba", reverse of the input String.

javin paul said...

@Suan, that's indeed a good solution without using recursion. Best part of this is that it doesn't need to reverse the whole string to check if given String is palindrome, as soon as you find one mismatched character you can say that its not palindrome. Great solution ..

Anonymous said...

CheckPalindrome method will not work.You have given

new StringBuilder(text);

and later appending the reverse of the string to the same stringbuilder sb.

So if my string is 676 the reversed string as per your prog will be 676676. How is it working for you? The Stringbuilder line should be

Stringbuilder sb = new StringBuilder();



Sahil Bharti said...

Here is solution in a simple way without using loop.
We are checking only first and last index.
String str="radar";
int j=str.length()-1;
if(str.charAt(0)==str.charAt(j))
System.out.println("String is Palindrome");
else
System.out.println("String is not Palindrome");

AnthX said...

how would that check the whole string Sahil? It looks like your code fragment would only check the first and last chacters.

Sahil Bharti said...

Anthony, There is no need to check the whole string using loop if first and last character of the string is same then your string is palindrome , e.g. "madam" is a palindrome string. Here is another logic but this has more time and space complexity.
System.out.println("Enter the string");
String str=new Scanner(System.in).nextLine();
String Result="";
for(int i=str.length()-1;i>=0;i--)
{
Result+=str.charAt(i);
}
System.out.println("\nReverse String of "+str+" is ="+Result);
if(Result.equals(str))
System.out.println("String is palindrome");
else
System.out.println("String is not palindrome");

AnthX said...

That makes much more sense in the second version, since you are checking the reverse of the string equalling the original string. Or if you just compared the nth char with the (length-1)th char. like, first compared to last, second compared to second-last, all the way to the middle.

Unless you just missed something in your first example. A palindrome is a word that reads the same forwards as it does backwards.

Unknown said...

Scanner input = new Scanner(System.in);
String z = null;
z = input.nextLine();
int StringLenght = z.length();

for(int i = 0; i < StringLenght/2; i++){
if(z.charAt(i) == z.charAt(StringLenght-1-i)){
System.out.println("The string is Palindrome:");
}
else
{
System.out.println("Not a Palindrome");
}
}

Post a Comment