Trong bài toán này, chúng ta được cung cấp một chuỗi có kích thước n. Và chúng ta phải in tất cả các hoán vị palindromic có thể được tạo ra bằng cách sử dụng các ký tự của chuỗi theo thứ tự bảng chữ cái. Nếu palindrome không được tạo bằng cách sử dụng chuỗi in ‘-1’.
Hãy lấy một ví dụ để hiểu rõ hơn về chủ đề -
Input: string = “abcba” Output : abcba bacba
Bây giờ, để giải quyết vấn đề này, chúng ta cần tìm tất cả các palindromes có thể và sau đó sắp xếp chúng theo thứ tự bảng chữ cái (thứ tự từ vựng). Hoặc một cách khác có thể là tìm palindrome đầu tiên về mặt từ vựng được tạo ra từ chuỗi. Sau đó, tìm palindrome tiếp theo tuần tự của chuỗi.
Đối với điều này, chúng tôi sẽ thực hiện các bước sau -
Bước 1 - lưu trữ tần suất xuất hiện của tất cả các ký tự của chuỗi.
Bước 2 - Bây giờ hãy kiểm tra xem chuỗi có thể tạo thành palindrome hay không. Nếu không có chữ IN “Không thể hình thành palindrome” và thoát ra. Nếu không thì làm -
Bước 3 - Tạo một chuỗi dựa trên logic rằng tất cả các ký tự có sự xuất hiện chẵn tạo thành một chuỗi và sự xuất hiện lẻ từ những ký tự khác. Và chúng tôi sẽ kẹp chuỗi lẻ giữa chuỗi chẵn (tức là ở dạng chuỗi chẵn + chuỗi lẻ + chuỗi chẵn).
Sử dụng nó, chúng ta có thể tìm thấy palindrome đầu tiên về mặt từ vựng. Sau đó, tìm tiếp theo bằng cách kiểm tra các kết hợp từ vựng đồng thời.
Ví dụ
CHƯƠNG TRÌNH minh họa khái niệm -
#include <iostream>
#include <string.h>
using namespace std;
const char MAX_CHAR = 26;
void countFreq(char str[], int freq[], int n){
for (int i = 0; i < n; i++)
freq[str[i] - 'a']++;
}
bool canMakePalindrome(int freq[], int n){
int count_odd = 0;
for (int i = 0; i < 26; i++)
if (freq[i] % 2 != 0)
count_odd++;
if (n % 2 == 0) {
if (count_odd > 0)
return false;
else
return true;
}
if (count_odd != 1)
return false;
return true;
}
bool isPalimdrome(char str[], int n){
int freq[26] = { 0 };
countFreq(str, freq, n);
if (!canMakePalindrome(freq, n))
return false;
char odd_char;
for (int i = 0; i < 26; i++) {
if (freq[i] % 2 != 0) {
freq[i]--;
odd_char = (char)(i + 'a');
break;
}
}
int front_index = 0, rear_index = n - 1;
for (int i = 0; i < 26; i++) {
if (freq[i] != 0) {
char ch = (char)(i + 'a');
for (int j = 1; j <= freq[i] / 2; j++) {
str[front_index++] = ch;
str[rear_index--] = ch;
}
}
}
if (front_index == rear_index)
str[front_index] = odd_char;
return true;
}
void reverse(char str[], int i, int j){
while (i < j) {
swap(str[i], str[j]);
i++;
j--;
}
}
bool nextPalindrome(char str[], int n){
if (n <= 3)
return false;
int mid = n / 2 - 1;
int i, j;
for (i = mid - 1; i >= 0; i--)
if (str[i] < str[i + 1])
break;
if (i < 0)
return false;
int smallest = i + 1;
for (j = i + 2; j <= mid; j++)
if (str[j] > str[i] && str[j] < str[smallest])
smallest = j;
swap(str[i], str[smallest]);
swap(str[n - i - 1], str[n - smallest - 1]);
reverse(str, i + 1, mid);
if (n % 2 == 0)
reverse(str, mid + 1, n - i - 2);
else
reverse(str, mid + 2, n - i - 2);
return true;
}
void printAllPalindromes(char str[], int n){
if (!(isPalimdrome(str, n))) {
cout<<"-1";
return;
}
do {
cout<<str<<endl;
} while (nextPalindrome(str, n));
}
int main(){
char str[] = "abccba";
int n = strlen(str);
cout<<”The list of palindromes possible is :\n”;
printAllPalindromes(str, n);
return 0;
} Đầu ra
Danh sách các palindromes có thể có là -
abccba acbbca baccab bcaacb cabbac cbaabc