Dada una string, necesitamos imprimir todos los palíndromos posibles que se pueden generar usando letras de esa string. Ejemplos:
Input: str = "aabcb"
Output: abcba bacab
Input: str = "aabbcadad"
Output: aabdcdbaa aadbcbdaa abadcdaba
abdacadba adabcbada adbacabda
baadcdaab badacadab bdaacaadb
daabcbaad dabacabad dbaacaabd
La generación de palíndromo se puede hacer siguiendo los pasos,
- Primero, debemos verificar si las letras de la string pueden hacer un palíndromo o no, si no, regresar.
- Después de la verificación anterior, podemos hacer la mitad de la primera string palíndromo (lexicográficamente más pequeña) tomando la mitad de la frecuencia de cada letra de la string dada.
- Ahora recorra todas las permutaciones posibles de esta media cuerda y cada vez agregue el reverso de esta parte al final y agregue un carácter de frecuencia impar en el medio si la string tiene una longitud impar, para hacer el palíndromo.
A continuación se muestra la implementación de C++.
C++
// C++ program to print all palindrome permutations of
// a string.
#include <bits/stdc++.h>
using namespace std;
#define M 26
/* Utility function to count frequencies and checking
whether letter can make a palindrome or not */
bool isPalin(string str, int* freq)
{
/* Initialising frequency array with all zeros */
memset(freq, 0, M * sizeof(int));
int l = str.length();
/* Updating frequency according to given string */
for (int i = 0; i < l; i++)
freq[str[i] - 'a']++;
int odd = 0;
/* Loop to count total letter with odd frequency */
for (int i = 0; i < M; i++)
if (freq[i] % 2 == 1)
odd++;
/* Palindrome condition :
if length is odd then only one letter's frequency must be odd
if length is even no letter should have odd frequency */
if ((l % 2 == 1 && odd == 1 ) || (l %2 == 0 && odd == 0))
return true;
else
return false;
}
/* Utility function to reverse a string */
string reverse(string str)
{
string rev = str;
reverse(rev.begin(), rev.end());
return rev;
}
/* Function to print all possible palindromes by letter of
given string */
void printAllPossiblePalindromes(string str)
{
int freq[M];
// checking whether letter can make palindrome or not
if (!isPalin(str, freq))
return;
int l = str.length();
// half will contain half part of all palindromes,
// that is why pushing half freq of each letter
string half = "";
char oddC;
for (int i = 0; i < M; i++)
{
/* This condition will be true at most once */
if(freq[i] % 2 == 1)
oddC = i + 'a';
half += string(freq[i] / 2, i + 'a');
}
/* palin will store the possible palindromes one by one */
string palin;
// Now looping through all permutation of half, and adding
// reverse part at end.
// if length is odd, then pushing oddCharacter also in mid
do
{
palin = half;
if (l % 2 == 1)
palin += oddC;
palin += reverse(half);
cout << palin << endl;
}
while (next_permutation(half.begin(), half.end()));
}
// Driver Program to test above function
int main()
{
string str = "aabbcadad";
cout << "All palindrome permutations of " << str << endl;
printAllPossiblePalindromes(str);
return 0;
}
Producción
All palindrome permutations of aabbcadad aabdcdbaa aadbcbdaa abadcdaba abdacadba adabcbada adbacabda baadcdaab badacadab bdaacaadb daabcbaad dabacabad dbaacaabd
Complejidad de tiempo: O((n/2)!), donde n es la longitud de la string y estamos encontrando todas las permutaciones posibles de la mitad.
Espacio Auxiliar: O(1)
Ilustración :
Let given string is "aabbcadad" Letters have following frequencies : a(4), b(2), c(1), d(2). As all letter has even frequency except one we can make palindromes with the letter of this string. Now half part is – aabd So traversing through all possible permutations of this half string and adding odd frequency character and reverse of string at the end we get following possible palindrome as final result : aabdcdbaa aadbcbdaa abadcdaba abdacadba adabcbada adbacabda baadcdaab badacadab bdaacaadb daabcbaad dabacabad dbaacaabd
Este artículo es una contribución de Utkarsh Trivedi.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA