이 문제에서는 크기가 n인 문자열이 제공됩니다. 그리고 문자열의 문자를 알파벳 순서로 사용하여 생성할 수 있는 모든 가능한 회문 순열을 인쇄해야 합니다. 문자열을 사용하여 회문을 생성하지 않은 경우 '-1'을 인쇄합니다.
주제를 더 잘 이해하기 위해 예를 들어 보겠습니다 -
Input: string = “abcba” Output : abcba bacba
이제 이 문제를 해결하려면 가능한 모든 회문을 찾아 알파벳순(사전순)으로 정렬해야 합니다. 또는 다른 방법은 문자열에서 만들어진 사전순으로 첫 번째 회문을 찾는 것일 수 있습니다. 그런 다음 시퀀스의 다음 회문을 순차적으로 찾습니다.
이를 위해 다음 단계를 수행합니다 -
1단계 - 문자열의 모든 문자의 발생 빈도를 저장합니다.
2단계 − 이제 문자열이 회문을 형성할 수 있는지 확인합니다. PRINT가 없으면 "회문을 형성할 수 없습니다"라고 표시하고 종료합니다. 그렇지 않으면 -
3단계 − 짝수 발생하는 모든 문자가 문자열을 구성하고 다른 문자에서 홀수 발생하는 논리를 기반으로 문자열을 만듭니다. 그리고 짝수 문자열 사이에 홀수 문자열을 끼워 넣습니다(예:even_string + odd_string + even_string 형식).
이것을 사용하여 사전순으로 첫 번째 회문을 찾을 수 있습니다. 그런 다음 동시 사전 조합을 확인하여 다음 항목을 찾습니다.
예
개념을 설명하는 프로그램 -
#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;
} 출력
가능한 회문 목록은 -
abccba acbbca baccab bcaacb cabbac cbaabc