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.
