22 February 2010

Find all possible palindromes in a String in Java C++

This is not the regular palindrome finder. Given a string, we should be able to print all the possible palindromes. Let me quickly give a brief example.
For the following text : abccbab
All the possible palindromes are,
bab
abccba
bccb
cc
If you could see there are two possible outcomes in palindrome, one is odd and other is even. My initial solution was very worse. What I actually did was did a permutation/combination of all the possible texts and send it to a palindrome() method. It will run in the worst possible time.
However, there is even a simpler solution available. First do a parse for odd occurring palindromes followed by even palindromes.
For odd palindromes run through each character from the text. For each character, see if there the pre and post occuring characters are equal, if they are equal print them and do the same for the next levels. In the following example shown below, assume you are at 'y' and see the previous and next characters are equal. If they are see further more until the palindrome functionality ceases. Print all of them whilst this time.
 

Thats it. Do the same for all the characters. Since there is no meaning in doing this for first and last characters, we can very well omit them.
Similar logic holds for even sized palindromes. Here we wont be holding the center character. Rest of the logic remains the same. The java code follows,

package dsa.stringmanipulation;

/**
 * Program to print all palindromes in a string
 * @author Bragaadeesh
 */
public class FindAllPalindromes {
 public static void main(String[] args){
  FindAllPalindromes finder = new FindAllPalindromes();
  finder.printAllPalindromes("abcddcbaABCDEDCBA");
 }
 
 public void printAllPalindromes(String inputText){
  if(inputText==null){
   System.out.println("Input cannot be null!");
   return;
  }
  if(inputText.length()<=2){
   System.out.println("Minimum three characters should be present");
  }
  //ODD Occuring Palindromes
  int len = inputText.length();
  for(int i=1;i<len-1;i++){
   for(int j=i-1,k=i+1;j>=0&&k<len;j--,k++){
    if(inputText.charAt(j) == inputText.charAt(k)){
     System.out.println(inputText.subSequence(j,k+1));
    }else{
     break;
    }
   }
  }
  //EVEN Occuring Palindromes
  for(int i=1;i<len-1;i++){
   for(int j=i,k=i+1;j>=0&&k<len;j--,k++){
    if(inputText.charAt(j) == inputText.charAt(k)){
     System.out.println(inputText.subSequence(j,k+1));
    }else{
     break;
    }
   }
  }

 }
}
/*
Sample Output:
DED
CDEDC
BCDEDCB
ABCDEDCBA
dd
cddc
bcddcb
abcddcba
*/

The code in C++
#include <iostream>
using namespace std;

void printAllPalindromes(char*);

char* subSequence(char*,int,int);

int main() {
 char *s = "abcddcbaABCDEDCBA";
 printAllPalindromes(s);
 return 0;
}

char* subSequence(char* mainSequence, int from, int to){
 char * tgt = new char[to-from+1];
 for(int i=0;i<(to-from);i++){
  tgt[i] = mainSequence[i+from];
 }
 tgt[to-from] = '\0';
 return tgt;
}

void printAllPalindromes(char* inputText) {
 if(!inputText) {
  printf("Input cannot be null!");
  return;
 }
 if(strlen(inputText)<=2) {
  printf("Minimum three characters should be present\n");
 }
 //ODD Occuring Palindromes
 int len = strlen(inputText);
 for(int i=1;i<len-1;i++) {
  for(int j=i-1,k=i+1;j>=0&&k<len;j--,k++) {
   if(inputText[j] == inputText[k]) {
    char* subSeq = subSequence(inputText,j,k+1);
    cout<<subSeq<<endl;
    delete subSeq;
   } else {
    break;
   }
  }
 }
 //EVEN Occuring Palindromes
 for(int i=1;i<len-1;i++) {
  for(int j=i,k=i+1;j>=0&&k<len;j--,k++) {
   if(inputText[j] == inputText[k]) {
    char* subSeq = subSequence(inputText,j,k+1);
    cout<<subSeq<<endl;
    delete subSeq;
   } else {
    break;
   }
  }
 }

}
/*
 Sample Output:
 DED
 CDEDC
 BCDEDCB
 ABCDEDCBA
 dd
 cddc
 bcddcb
 abcddcba
 */

Cheers,
Bragaadeesh.

12 comments:

ifanchu said...

Hi, I am wondering why you're have the condition check at line 18 of Java code to check if the length of the given text is less than or equal to 2. Isn't a word like "cc" a palindrom as well? Anyways, thanks for the post, it helps.

BragBoy said...

@Van:
Yes "cc" is also a palindrome. You can have that line as well. But a palindrome would look proud and decent if it has at least 3 characters in it :)
Thanks for stopping by!

Spider said...

Very useful blog!

A minor thing --

In Java impl, the even outer loop should start from 0 instead of 1. Can be tested with
"aacddcbaABCDEDCBA" and the current program doesn't print aa.

Thanks again!

BragBoy said...

@Spider: Thanks for stopping by and your comments!!!

nagarajan said...

Hi Bragadeesh,

I was searching for a O(n2) solution for the longest palindrome problem for more than one week. Not able to find an understandable solution.

Thank you so much for your clear explanation :-)

Your blog is very useful and please keep up your good work!

BragBoy said...

Thanks Nagarajan for checking out!

Gaurav Aggarwal said...

Your code fails for "aab".
Change the initial value of i to 0 in the for loop for even number. It will solve the problem.

Jash said...
This comment has been removed by the author.
Jash said...

Hi, What if i dont want to print the palindromes which are part of a big palindrome. Can u provide with its code too?

BragBoy said...

@Prasad Prabu: You're most welcome!

vij said...
This comment has been removed by the author.
vij said...

What is the complexity?