Minimiser le remplacement d'un caractère par la lettre la plus proche, faisant de la chaîne un palindrome

Dans cet article, nous aborderons un problème algorithmique intéressant : "Minimiser le remplacement des caractères par leur alphabet le plus proche pour créer un palindrome de chaîne." Ce problème est intéressant car il implique des opérations de chaîne, la vérification du palindrome et le concept de caractère. Valeurs ASCII. Approfondissons cette question.

Énoncé du problème

Étant donné une chaîne, la tâche est de la convertir en palindrome avec un minimum de substitutions. Ces substitutions sont réalisées en remplaçant les caractères par leur alphabet le plus proche.

Comprendre le problème

Un palindrome est un mot, une phrase, un nombre ou une autre séquence de caractères qui est lu à l'envers de la même manière qu'en avant. Notre objectif est de minimiser le nombre total de substitutions nécessaires pour convertir une chaîne donnée en palindrome.

Par exemple, considérons la chaîne "abc". Pour le convertir en palindrome, on peut remplacer « c » par « a », ce qui nécessite deux substitutions (« c » par « b » et « b » par « a »). Le nombre minimum de remplacements est donc de 2.

Méthode algorithmique

Pour résoudre ce problème, nous utiliserons la méthode à deux pointeurs. Voici les étapes -

• Initialisez deux pointeurs, un au début de la chaîne et l'autre à la fin de la chaîne.

• Comparez les caractères au pointeur.

• Si égal, déplacez le pointeur vers l’intérieur.

• S'ils ne sont pas égaux, remplacez le caractère le plus éloigné de « a » par le caractère le plus proche et augmentez le nombre de substitutions. Déplacez également le pointeur vers l’intérieur.

• Répétez les étapes 2 à 4 jusqu'à ce que le pointeur de début ne soit pas inférieur au pointeur de fin.

Exemple

C'est le code C++ qui implémente la méthode ci-dessus -

#include<bits/stdc++.h>
using namespace std;

int makePalindrome(string str) {
   int len = str.size();
   int res = 0;
   for (int i = 0, j = len - 1; i < j; i++, j--) {
      res += abs(str[i] - str[j]);
   }
   return res;
}

int main() {
   string str="abcde";
   cout << "Minimum replacements: " << makePalindrome(str);
   return 0;
}

Sortie

Minimum replacements: 6

Exemple de cas de test

Prenons un exemple -

Considérez la chaîne "abcde". Le programme ci-dessus affichera « Remplacements minimum : 4 ». C'est pourquoi -

• Comparez « a » et « e ». Ce ne sont pas les mêmes, alors remplacez « e » par « a ». Cela a nécessité 4 remplacements. Notre chaîne est maintenant "abcda".

• Comparez "b" et "d". Ce ne sont pas les mêmes, alors remplacez « d » par « b ». Cela nécessite 2 remplacements. Notre chaîne est désormais "abcba".

• Maintenant, la corde est un palindrome. Par conséquent, le nombre total minimum de substitutions est de 4 + 2 = 6.

N'oubliez pas que le nombre de substitutions est calculé en fonction de la différence absolue des valeurs ASCII des caractères.

Conclusion

Cette question est un bon exemple de la façon dont une simple manipulation de chaînes et des techniques à deux pointeurs peuvent résoudre un problème relativement complexe. Connaître ces questions vous aidera non seulement à coder les entretiens, mais améliorera également vos compétences globales en résolution de problèmes.

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!