Cho chuỗi, in tất cả hoán vị palindrome có thể tạo từ các ký tự của chuỗi.
Input: 'aabb' Output: abba baab
Giải pháp: Kiểm tra có tạo palindrome được không. Tạo nửa chuỗi, sinh hoán vị của nửa, gắn nửa đảo ngược (và ký tự lẻ ở giữa nếu độ dài lẻ).
Chương trình minh họa
#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++;
return (l % 2 == 1 && odd == 1) || (l % 2 == 0 && odd == 0);
}
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 << "Tất cả hoán vị palindrome của " << str << ":\n";
generatePalindromePermutation(str);
return 0;
}
Kết quả
abba baab