JavaBeat

  • Home
  • Java
    • Java 7
    • Java 8
    • Java EE
    • Servlets
  • Spring Framework
    • Spring Tutorials
    • Spring 4 Tutorials
    • Spring Boot
  • JSF Tutorials
  • Most Popular
    • Binary Search Tree Traversal
    • Spring Batch Tutorial
    • AngularJS + Spring MVC
    • Spring Data JPA Tutorial
    • Packaging and Deploying Node.js
  • About Us
    • Join Us (JBC)
  • Privacy
  • Contact Us

How To Use The Palindrome Function In Java – Methods And Examples

October 26, 2018 by Krishna Srinivasan Leave a Comment

How To Use The Palindrome Function in Java

You know what a palindrome is, right?

A palindrome is a phrase or sentence that reads the same forward and backward, such as “Madam, I’m Adam” or “dammit I’m mad” or “a man, a plan, a canal, Panama.”

Quick Navigation
Longest Palindromic Substring
Manacher’s Algorithm and Palindrome Function in Java
Examples of Palindrome Function in Java
Manacher’s Algorithm: Case in Point
Some Final Thoughts About Palindrome Function in Java

Longest Palindromic Substring

Computer science goes into the concept of longest palindromic substring, or longest symmetric factor. This is the problem of finding the longest substring of any string that also reads as a palindrome.

Consider the word “bananas” – the “anana” of that is a palindrome. In the word “abracadabra,” the entire word isn’t a palindrome but “aca” and “ada” within that word are palindromic. When taking this approach, it’s sometimes necessary to look at all palindromic substrings that stand alone and can’t be extended or connected to other, longer palindromic substrings.

In the 70s, Glenn Manacher developed an algorithm and set of rules for palindromes that appear at the start of any given string. Later researchers found that this same algorithm can be used to determine all palindromic substrings anywhere in the original input string (both of these are linear time solutions).

Manacher’s Algorithm and Palindrome Function in Java

This algorithm can be considered as a set of ground rules for observations and characteristics of a palindrome and sub-palindrome:

  • When considering palindrome function in Java, the left side of a palindrome must be the mirror image of the right side
  • A third palindrome that is within the right side of a first palindrome will be the exact same length as a second palindrome that’s positioned at the center on the left side. That is, if the second palindrome is still within the limits of the first palindrome by one character, or doesn’t extend to the left bound of the first palindrome
  • When a second palindrome meets up with or goes beyond the left bound of the first palindrome, the interval from the center of the second palindrome to the left bound of the first should be exactly equal to the interval from the third palindrome’s center to the first palindrome’s right bound
  • In an example like that above, the third palindrome’s length can be determined as the next character after the character at the right bound of the first palindrome. It can then be compared with its mirror character at the third palindrome’s center
  • When determining the palindromic length of a fourth palindrome, when its center is outside the right bound of the first palindrome, neither the first nor second palindrome can be used to determine that length
  • When determining the palindromic length of a substring, the first palindrome can be thought of as a reference with characters farthest to the right in a string

Examples of Palindrome Function in Java

Let’s say that s is a string of N characters. In this case, s2 can be considered a derived string of s, with N * 2 + 1 elements.

Each element should correspond to one or more of the following:

  • The N characters in s
  • The N-1 boundaries among these characters
  • Any boundaries before or after the first and last character

A boundary in s2 can be considered equal to any other boundary in s2, when it comes to matching elements and determining palindromic length. For the array of palindromic span for the elements in s2, from center to either outermost bound, each boundary should be counted toward palindromic length.

In other words, a palindrome that has a palindromic span of 1 would be three elements in length. This would be represented as p in our example.

For the position of the center of the palindrome that includes a boundary closest to the right bound of s2, that will be represented by c in our example, i.e. p[c]*2+1. The position of the rightward boundary of this palindrome will be represented by r, i.e. r = c+p[c]. For the position of a character or boundary in s2 with a palindromic span that has yet to be determined, that should be represented by i in our example, with i always being to the right of c. i2, then, is the mirrored position of i around c, i.e. {i, i2} = {6,4}, {7,3}, {8,2}, when c = 5

Manacher’s Algorithm: Case in Point

char[] s2 = addBoundaries(s.toCharArray());

int[] p = new int[s2.length];

int c = 0, r = 0; // Here the first element in s2 has been processed.

int m = 0, n = 0; // The walking indices to compare if two elements are the same

for (int i = 1; i<s2.length; i++) {

if (i>r) {

p[i] = 0; m = i-1; n = i+1;

} else {

int i2 = c*2-i;

if (p[i2]<(r-i-1)) {

p[i] = p[i2];

m = -1; // This signals bypassing the while loop below.

} else {

p[i] = r-i;

n = r+1; m = i*2-n;

}

}

while (m>=0 && n<s2.length && s2[m]==s2[n]) {

p[i]++; m--; n++;

}

if ((i+p[i])>r) {

c = i; r = i+p[i];

}

}

int len = 0; c = 0;

for (int i = 1; i<s2.length; i++) {

if (len<p[i]) {

len = p[i]; c = i;

}

}

char[] ss = Arrays.copyOfRange(s2, c-len, c+len+1);

return String.valueOf(removeBoundaries(ss));

}

private static char[] addBoundaries(char[] cs) {

if (cs==null || cs.length==0)

return "||".toCharArray();

char[] cs2 = new char[cs.length*2+1];

for (int i = 0; i<(cs2.length-1); i = i+2) {

cs2[i] = '|';

cs2[i+1] = cs[i/2];

}

cs2[cs2.length-1] = '|';

return cs2;

}

private static char[] removeBoundaries(char[] cs) {

if (cs==null || cs.length<3)

return "".toCharArray();

char[] cs2 = new char[(cs.length-1)/2];

for (int i = 0; i<cs2.length; i++) {

cs2[i] = cs[i*2+1];

}

return cs2;

}

}

Determining If a String is a Palindrome

In these cases, each character can be looped and checked against the character on the opposite side. The problem with this approach is that half the work is unnecessary, as each character is being checked twice.

In the English palindrome “madam,” the algorithm would check each letter as a character, when all that really needs to be compared are the first two characters and last two characters – the middle one would not need to be checked.

Checking for Palindrome String Using Recursion (Courtesy Beginnersbook)

package beginnersbook.com;

import java.util.Scanner;

class PalindromeCheck

{

//My Method to check

public static boolean isPal(String s)

{ // if length is 0 or 1 then String is palindrome

if(s.length() == 0 || s.length() == 1)

return true;

if(s.charAt(0) == s.charAt(s.length()-1))

/* check for first and last char of String:

* if they are same then do the same thing for a substring

* with first and last char removed. and carry on this

* until you string completes or condition fails

* Function calling itself: Recursion

*/

return isPal(s.substring(1, s.length()-1));

/* If program control reaches to this statement it means

* the String is not palindrome hence return false.

*/

return false;

}

public static void main(String[]args)

{

//For capturing user input

Scanner scanner = new Scanner(System.in);

System.out.println("Enter the String for check:");

String string = scanner.nextLine();

/* If function returns true then the string is

* palindrome else not

*/

if(isPal(string))

System.out.println(string + " is a palindrome");

else

System.out.println(string + " is not a palindrome");

}

}

Output 1:

Enter the String for check:

qqaabb

qqaabb is not a palindrome

Output 2:

Enter the String for check:

cocoococ

cocoococ is a palindrome

Some Final Thoughts About Palindrome Function in Java

 Palindrome Function in Java

To sum up, your task with palindromes is to compare characters at the left and right ends of a string. If they don’t match, the string itself isn’t a palindrome. The next step is to compare the two characters that are second to the left and right ends of a string, then continue toward the center of the string or until you find a pair that don’t match.

If you reach the middle of the string, then you do have a palindrome – or at least part of that string can be considered a palindrome. If the string is “madam,” the entire string is a palindrome. If the string is “amadam,” it’s not a palindrome but the “ada” toward the center can be considered as a palindrome.

Filed Under: Java Tagged With: palindrome function, palindrome function in Java

About Krishna Srinivasan

He is Founder and Chief Editor of JavaBeat. He has more than 8+ years of experience on developing Web applications. He writes about Spring, DOJO, JSF, Hibernate and many other emerging technologies in this blog.

Leave a Reply Cancel reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.

Follow Us

  • Facebook
  • Pinterest

As a participant in the Amazon Services LLC Associates Program, this site may earn from qualifying purchases. We may also earn commissions on purchases from other retail websites.

JavaBeat

FEATURED TUTORIALS

Answered: Using Java to Convert Int to String

What is new in Java 6.0 Collections API?

The Java 6.0 Compiler API

Copyright © by JavaBeat · All rights reserved