ในปัญหานี้ เราได้รับสตริงและเราต้องพิมพ์การเรียงสับเปลี่ยน palindromic ทั้งหมดที่เป็นไปได้จากอักขระของสตริงนั้น
มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน −
อินพุต - string ='aabb'
ผลลัพธ์ − แอบบ้า
เพื่อแก้ปัญหานี้ เราต้องใช้อักขระของสตริง และสร้างสตริง palindrome ทั้งหมดโดยใช้อักขระเหล่านี้ทีละตัว
ขั้นตอนที่ 1 − ตรวจสอบว่าสตริงนั้นเป็นพาลินโดรมหรือไม่ พิมพ์ 'เป็นไปไม่ได้ ’ ถ้าไม่ใช่
ขั้นตอนที่ 2 − ถ้ามันสามารถสร้าง palindrome ได้ ให้ทำครึ่งหนึ่งและเลือกตัวอักษรของสตริงทีละตัว
ขั้นตอนที่ 3 − ข้ามผ่านพีชคณิตที่สร้างขึ้นและย้อนกลับครึ่งด้านสำหรับสตริงที่มีความยาวเท่ากัน และสำหรับความถี่คี่ อักขระคี่ควรอยู่ตรงกลางเพื่อสร้าง palindrome
ขั้นตอนที่ 4 − พิมพ์ palindrome ทั้งหมดที่สร้างขึ้น
โปรแกรมที่จะใช้อัลกอริทึม -
ตัวอย่าง
#include <bits/stdc++.h>
using namespace std;
#define M 26
bool isPalindrome(string str, int* freq){
memset(freq, 0, M * sizeof(int));
int l = str.length();
for (int i = 0; i < l; i++)
freq[str[i] - 'a']++;
int odd = 0;
for (int i = 0; i < M; i++)
if (freq[i] % 2 == 1)
odd++;
if ((l % 2 == 1 && odd == 1 ) || (l %2 == 0 && odd == 0))
return true;
else
return false;
}
string reverse(string str){
string rev = str;
reverse(rev.begin(), rev.end());
return rev;
}
void generatePalindromePermutation(string str){
int freq[M];
if (!isPalindrome(str, freq))
return;
int l = str.length();
string half ="";
char oddC;
for (int i = 0; i < M; i++) {
if(freq[i] % 2 == 1)
oddC = i + 'a';
half += string(freq[i] / 2, i + 'a');
}
string palindrome;
do {
palindrome = half;
if (l % 2 == 1)
palindrome += oddC;
palindrome += reverse(half);
cout<<palindrome<<endl;
}
while (next_permutation(half.begin(), half.end()));
}
int main() {
string str="abab";
cout<<"All palindrome permutations of "<<str<<" are :\n";
generatePalindromePermutation(str);
return 0;
} ผลลัพธ์
All palindrome permutations of abab are : abba baab
