Réorganiser les caractères pour former un palindrome (si possible) en C++

Nous recevons une chaîne « str » d'une longueur donnée. La tâche consiste à réorganiser les caractères afin que la sortie devienne une chaîne palindrome sans ajouter ni supprimer de caractères de la chaîne d'entrée donnée. Une chaîne palindrome, c'est lorsque les caractères sont disposés de telle manière qu'ils sonnent de la même manière du début à la fin.

Regardons différents scénarios d'entrée et de sortie pour cela -

Input - String str = "itnin"

Output - Si possible, le réarrangement des caractères pour former une chaîne palindrome est : nitin

Explication - On nous donne une variable de type string, disons str. Nous allons maintenant réorganiser les caractères de la chaîne d'entrée pour en faire une chaîne palindrome sinon

Input - String str = "baaaba"

Output - Le résultat d'un éventuel réarrangement de caractères pour former un palindrome est : aabbaa

Explication - On nous donne une variable de type string, disons str. Nous allons maintenant réorganiser les caractères de la chaîne d'entrée pour en faire une chaîne palindrome et renvoyer 'NON POSSIBLE' si cela n'est pas possible. Par conséquent, la sortie donnée par la chaîne d’entrée est « aabbaa ».

La méthode utilisée dans le programme ci-dessous est la suivante

• Entrez une variable de type chaîne, en supposant qu'elle soit str, calculez la taille de la chaîne et stockez-la dans une variable nommée longueur.

• Passez les données à la fonction Rearrangement(str, length).

• À l'intérieur de la fonction Rearrangement(arr, length)

  • créez une variable de type unordered_map nommée 'um', qui stocke les paires clé-valeur de types char et entier.

  • Déclarez un total de variable de type entier et définissez-le sur 0.

  • Créez une variable de type caractère 'ch' et des variables de type chaîne str_1 et str_2.

  • Commencez par une boucle de i à 0 jusqu'à ce que i soit inférieur à la longueur. Dans la boucle, définissez um[str[i]] en incrémentant la valeur 1.

  • Démarrez la boucle FOR pour parcourir la carte 'um'. À l'intérieur de la boucle, vérifiez SI it.second % 2 n'est pas égal à 0, puis augmentez le total de 1 et définissez ch dessus.first.

  • Vérifiez SI le total est supérieur à 1 ou total = 1 et longueur % 2 = 0, alors 0 est renvoyé.

  • Démarrez la boucle FOR pour parcourir la carte 'um'. Dans la boucle, str(it.second / 2, it.first) est défini sur str, str_1 est défini sur str_1 + str et str_2 est défini sur str + str_2.

  • Vérifiez SI total = 1, puis retournez str_1 + ch + str_2. Sinon, str_1 + str_2 est renvoyé.

• Imprimez les résultats.

Exemple

#include <bits/stdc++.h>
using namespace std;
string Rearrangement(string str, int length){
   unordered_map<char, int> um;
   int total = 0;
   char ch;
   string str_1 = "";
   string str_2 = "";

   for (int i = 0; i < length; i++){
      um[str[i]]++;
   }
   for(auto it : um){
      if(it.second % 2 != 0){
         total++;
         ch = it.first;
      }
   }
   if(total > 1 || total == 1 && length % 2 == 0){
      return 0;
   }
   for(auto it : um){
      string str(it.second / 2, it.first);
      str_1 = str_1 + str;
      str_2 = str + str_2;
   }
   if(total == 1){
      return str_1 + ch + str_2;
   }
   else{
      return str_1 + str_2;
   }
}
int main(){
   string str = "itnin";
   int length = str.size();
   cout<<"Rearrangement of characters to form palindrome if possible is: "<<Rearrangement(str, length);
   return 0;
}

Output

Si nous exécutons le code ci-dessus, la sortie suivante sera générée

Rearrangement of characters to form palindrome if possible is: nitin

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!