Trong bài toán này, chúng ta được cung cấp một chuỗi và chúng ta phải in tất cả các hoán vị palindromic có thể từ các ký tự của chuỗi đó.
Hãy lấy một ví dụ để hiểu vấn đề -
Đầu vào - string =‘aabb’
Đầu ra - abba baab
Để giải quyết vấn đề này, chúng ta phải lấy các ký tự của chuỗi và lần lượt tạo ra tất cả các chuỗi palindrome bằng cách sử dụng các ký tự này.
Bước 1 - Kiểm tra xem chuỗi có phải là palindrome hay không, in ‘ Không thể xảy ra 'Nếu không.
Bước 2 - Nếu nó có thể tạo ra palindrome, hãy chia nó thành một nửa và chọn từ điển từng chữ cái của chuỗi.
Bước 3 - Duyệt qua các hoán vị đã tạo và đảo ngược nửa bên đối với chuỗi có độ dài chẵn và đối với tần số lẻ, ký tự lẻ phải ở giữa để tạo ra một palindrome.
Bước 4 - in tất cả palindrome đã tạo.
Chương trình triển khai thuật toán -
Ví dụ
#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;
} Đầu ra
All palindrome permutations of abab are : abba baab