5 Ways to Check for a Palindrome String in Java

Solving the palindrome string problem in Java involves checking whether a given string reads the same forwards and backward. There are several approaches to solving this problem, each with its own merits. Let’s explore these solutions with a diagram, code examples, and explanations of each.

Key Steps:

• A palindrome string is one where the characters from the start to the middle mirror the characters from the end to the middle (e.g., “level”, “racecar”, “noon”, “madam”).
• Approaches to solving it can involve iterating over the string, using recursion, or employing data structures like stacks.

1. Two-Pointer Approach (Iterative Solution)

Explanation:

In this approach, two pointers are used: one starting at the beginning of the string and the other at the end. You compare characters from both ends, moving the pointers inward until they meet in the middle.

Steps:

• Initialize two pointers: left at the start of the string and right at the end.
• Compare the characters in these two positions.
• If they match, move the pointers inward (increment left and decrement right).
• If all corresponding characters match, the string is a palindrome.

Code:

public class PalindromeString1 {
    public static boolean isPalindrome(String str) {
        int left = 0;
        int right = str.length() - 1;

        while (left < right) {
            // If characters don't match, not a palindrome
            if (str.charAt(left) != str.charAt(right)) {
                return false;  
            }
            left++;
            right--;
        }
        return true;
    }

    public static void main(String[] args) {
        String str = "madam";
        System.out.println(isPalindrome(str));  // Output: true
    }
}

Diagram:

Example: "madam"

Pointer positions:
[m][a][d][a][m]
 ↑             ↑
left          right

Match: left = right -> move pointers inward

[m][a][d][a][m]
     ↑     ↑

All characters match: "madam" is a palindrome.

2. String Reversal Approach

Explanation:

This approach involves reversing the original string and comparing it to the original. If both the reversed string and the original string are identical, the string is a palindrome.

Steps:

• Reverse the string.
• Compare the reversed string with the original string.
• If they are the same, the string is a palindrome.

Code:

public class PalindromeString2 {
    public static boolean isPalindrome(String str) {
        String reversed = new StringBuilder(str).reverse().toString();
        // Compare original and reversed strings
        return str.equals(reversed);
    }

    public static void main(String[] args) {
        String str = "racecar";
        System.out.println(isPalindrome(str));  // Output: true
    }
}

Diagram:

Example: "racecar"

Original:  "racecar"
Reversed:  "racecar"

Both are the same: "racecar" is a palindrome.

3. Recursive Approach

Explanation:

This approach uses recursion to solve the problem by comparing the first and last characters of the string. If they match, the recursion continues with the substring that excludes the first and last characters, until the base case is reached (an empty or single-character string).

Steps:

• Compare the first and last characters of the string.
• If they are the same, call the function recursively on the substring excluding those characters.
• If the base case is reached (string length is 0 or 1), return true because the string is a palindrome.

Code:

public class PalindromeString3 {
    public static boolean isPalindrome(String str) {
        // If single character or empty string
        if (str.length() <= 1) {
            return true;
        }
        
        // If first and last characters don't match
        if (str.charAt(0) != str.charAt(str.length() - 1)) {
            return false;
        }
        // Recursive call
        return isPalindrome(str.substring(1, str.length() - 1));
    }

    public static void main(String[] args) {
        String str = "level";
        System.out.println(isPalindrome(str));  // Output: true
    }
}

Diagram:

Example: "level"

Step 1: "level" -> Compare 'l' and 'l' -> Match -> Check "eve"
Step 2: "eve"   -> Compare 'e' and 'e' -> Match -> Check "v"
Step 3: "v"     -> Single character, base case -> Palindrome

4. Stack and Queue Approach

Explanation:

This approach involves using a stack (Last-In-First-Out) and a queue (First-In-First-Out) to check for a palindrome. By pushing characters onto the stack and enqueueing them into a queue, we can compare the characters removed from both data structures.

Steps:

• Push each character of the string onto a stack and enqueue each character into a queue.
• Pop from the stack and dequeue from the queue simultaneously, comparing the characters.
• If all the characters match, the string is a palindrome.

Code:

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

public class PalindromeString4 {
    public static boolean isPalindrome(String str) {
        Stack<Character> stack = new Stack<>();
        Queue<Character> queue = new LinkedList<>();

        for (char c : str.toCharArray()) {
            stack.push(c);
            queue.add(c);
        }

        while (!stack.isEmpty()) {
            // If characters don't match
            if (stack.pop() != queue.remove()) {
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        String str = "deified";
        System.out.println(isPalindrome(str));  // Output: true
    }
}

Diagram:

Example: "deified"

Stack (LIFO): [d][e][i][f][i][e][d]
Queue (FIFO): [d][e][i][f][i][e][d]

Compare popped from stack with dequeued from queue:
    'd' == 'd'
    'e' == 'e'
    'i' == 'i'
    ...

All characters match: "deified" is a palindrome.

5. Character-by-Character Comparison (Custom Loop)

Explanation:

In this approach, a simple loop compares the first and last characters of the string, then the second and second-last characters, and so on until the middle is reached. It’s similar to the two-pointer approach but uses a custom loop for character comparison.

Steps:

• Loop through half the string.
• Compare characters from the start and end moving inward.
• If any character doesn’t match, the string is not a palindrome.

Code:

public class PalindromeString5 {
    public static boolean isPalindrome(String str) {
        int n = str.length();
        for (int i = 0; i < n / 2; i++) {
            // If characters don't match
            if (str.charAt(i) != str.charAt(n - i - 1)) {
                return false;  
            }
        }
        return true;
    }

    public static void main(String[] args) {
        String str = "noon";
        System.out.println(isPalindrome(str));  // Output: true
    }
}

Diagram:

Example: "noon"

Compare:
    'n' == 'n' -> Match
    'o' == 'o' -> Match

All characters match: "noon" is a palindrome.

Summary of Solutions:

Each approach is efficient for solving the palindrome string problem, but the two-pointer approach and string reversal approach are commonly preferred due to their simplicity and clarity.

People Also Ask For,

1. What is a palindrome string?

A palindrome string is a word or phrase that reads the same forwards and backward, ignoring spaces, punctuation, and capitalization (e.g., “civic”, “level”).

2. How can you check if a string is a palindrome in Java?

You can check if a string is a palindrome by using the two-pointer approach to compare characters from both ends or by reversing the string and comparing it with the original.

3. Can you solve a palindrome string problem using recursion in Java?

Yes, you can solve it recursively by comparing the first and last characters of the string and then recursively checking the substring without them.

4. Is there a way to check a palindrome string without reversing the string?

Yes, you can use the two-pointer technique or a custom loop to compare characters from the start and end of the string without reversing it.

5. What is the time complexity of checking if a string is a palindrome in Java?

The time complexity of most palindrome-checking algorithms (two-pointer, string reversal, recursion) is O(n), where n is the length of the string.

6. Can you use a stack to check for a palindrome in Java?

Yes, you can use a stack to push characters and compare them with characters from a queue or the original string to check if it’s a palindrome.

7. Which is the most efficient way to check a palindrome string?

The most efficient ways are the two-pointer approach or string reversal, both having a time complexity of O(n) and being easy to implement.

8. Can palindrome checking be case-insensitive in Java?

Yes, by converting the string to lower or upper case using toLowerCase() or toUpperCase() before performing the palindrome check.

You May Also Like These,

All HackerRank Solutions in Java
Java Interview Preparation