พิมพ์ Palindrome Permutations ทั้งหมดของสตริงใน C++

ในปัญหานี้ เราจะได้รับสตริง และต้องพิมพ์ palindromic permutations ทั้งหมดที่เป็นไปได้จากตัวอักษรของสตริงนั้น

ตัวอย่างเพื่อความเข้าใจ

Input - string = 'aabb'

Output - abba baab

เพื่อแก้ปัญหานี้ เราต้องนำตัวอักษรของสตริงมาทีละตัวและสร้าง palindrome strings ทั้งหมดโดยใช้ตัวอักษรเหล่านี้

ขั้นตอนที่ 1 - ตรวจสอบว่าสตริงเป็น palindrome ได้หรือไม่ พิมพ์ 'Not Possible' ถ้าไม่ได้

ขั้นตอนที่ 2 - ถ้าสร้าง palindrome ได้ ให้แบ่งครึ่งและเลือกตัวอักษรแต่ละตัวของสตริงแบบ lexicographically

ขั้นตอนที่ 3 - ท่องผ่าน permutations ที่สร้างขึ้นและกลับด้านครึ่งหนึ่งสำหรับสตริงความยาวคู่ และสำหรับความถี่คี่ ตัวอักษรคี่ควรอยู่กลางเพื่อสร้าง palindrome

ขั้นตอนที่ 4 - พิมพ์ palindromes ทั้งหมดที่สร้างขึ้น

โปรแกรมตัวอย่าง

#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