Le nombre minimum de caractères qui doivent être remplacés pour que les chaînes soient concaténées en une chaîne palindrome de longueur K

Le suivi du nombre minimum de caractères pour convertir une chaîne donnée en un lien de sous-chaînes palindromiques de longueur K est un problème courant dans le domaine du contrôle de chaînes. Une chaîne lue selon les mêmes étapes et inversée est appelée chaîne palindrome. Par exemple, « radar » ou « niveau ». Cet article couvrira les concepts de base, les méthodes et les stratégies d'optimisation potentielles pour résoudre efficacement ce problème. À la conclusion de cet article, les lecteurs seront en mesure de gérer des problèmes similaires de manipulation de chaînes car ils auront une compréhension complète des étapes requises.

Le problème sera expliqué en détail dans les paragraphes suivants, puis les avantages et les inconvénients de chaque méthode seront discutés. Les méthodes sélectionnées sont examinées minutieusement et des exemples de code sont fournis pour montrer comment les utiliser. Nous examinerons également la complexité temporelle de chaque méthode pour voir leur efficacité sous différents nombres d'entrées.

Méthode à utiliser

• Méthode Brute-Force

• Approche par fenêtre coulissante

La traduction chinoise de

Approche par Force Brute

est :

Approche par Force Brute

La Brute-Force L'approche pour trouver le moins de caractères à supplanter pour former une concaténation de chaîne d'une chaîne palindromique de longueur K comprend la vérification de toutes les sous-chaînes possibles de longueur K dans la chaîne donnée. Cela suit les étapes : définir deux pointeurs, effacé vers la droite, jusqu'au début et à la fin de la sous-chaîne de caractères K, initialisez une variable pour suivre les moindres substitutions et parcourez la chaîne, en mettant à niveau la fenêtre avec le pointeur approprié se déplaçant d'un pas vers la droite à chaque fois. vérifiez s'il pourrait s'agir d'un palindrome en comparant les caractères de gauche et de droite, et comptez le nombre de substitutions requises au cas où ce ne serait pas un palindrome. Gardez une trace du moins de remplacements trouvés jusqu'à présent. Poursuivez cette préparation jusqu'à la conclusion. de la chaîne. Le résultat sera le moins de substitutions nécessaires pour réaliser la sous-chaîne palindromique de longueur K spécifiée. Dans tous les cas, cette approche a une complexité temporelle élevée, ce qui la rend inutile pour des chaînes énormes.

Algorithme

• Considérez chaque sous-chaîne de longueur K lorsque vous parcourez la chaîne fournie.

• Vérifiez si chaque sous-chaîne est un palindrome

• Comptez combien de caractères devraient être modifiés s'il ne s'agissait pas déjà d'un palindrome.

• Conservez le moins de sous-chaînes possible qui doivent être remplacées

• Créez un palindrome en modifiant les caractères de la sous-chaîne de remplacement minimale.

Exemple

#include <iostream>
#include <string>
using namespace std;

string minimalReplacementPalindromeSubstring(const string& str, int K) {
   int n = str.length();
   string minReplacementSubstr;

   for (int i = 0; i <= n - K; i++) {
      string substr = str.substr(i, K);
      int replacements = 0;
      for (int j = 0; j < K / 2; j++) {
         if (substr[j] != substr[K - 1 - j]) {
            replacements++;
         }
      }

      if (replacements < minReplacementSubstr.length() || minReplacementSubstr.empty()) {
         minReplacementSubstr = substr;
      }
   }

   return minReplacementSubstr;
}

int main() {
   string input = "iurefhuhfrati";
   int K = 4;

   string result = minimalReplacementPalindromeSubstring(input, K);
   cout << "Minimal Replacement Substring: " << result << endl;

   return 0;
}

Sortie

Minimal Replacement Substring: rati

Méthode de la fenêtre coulissante

L'approche de la fenêtre glissante peut être utilisée pour résoudre efficacement des problèmes, y compris des opérations de sous-tableaux ou de sous-chaînes. Dans le cas d'une concaténation de chaînes recherchant le nombre minimum de caractères pour créer une chaîne palindrome de longueur K, la méthode consiste à maintenir une fenêtre (sous-chaîne) de taille fixe de K caractères lors de la navigation dans la chaîne d'entrée.

Le calcul définit deux pointeurs « gauche » et « droite », indiquant initialement le début et la fin de la sous-chaîne de caractères K. Il détermine ensuite le nombre de substitutions nécessaires pour convertir cette sous-chaîne en palindrome. Pour garder une trace du nombre minimum de remplacements requis, une variable 'min_replacements' est initialisée.

Algorithme

• Définissez deux pointeurs, gauche et droite, pointant respectivement vers le début et la fin de la sous-chaîne de caractères K principale.

• Détermine le nombre de substitutions attendues pour convertir une sous-chaîne en palindrome.

• Pour garder une trace du nombre minimum de remplacements requis, initialisez la variable min_replacements

• Mettez à jour la fenêtre en déplaçant le pointeur droit d'une position vers la droite

• Si la fenêtre actuelle est un palindrome, déplacez le pointeur droit

• Calculez le nombre de remplacements requis et, si nécessaire, modifiez min_replacements si la fenêtre actuelle n'est pas un palindrome.

• Pour mettre à jour la fenêtre, déplacez le pointeur gauche d'un espace vers la droite.

• Jusqu'à la conclusion de la chaîne, répétez les étapes 4 à 7.

• Les caractères de la sous-chaîne doivent être remplacés par le moins de substitutions possible

Exemple

#include <iostream>
#include <string>
using namespace std;

int minReplacementsForPalindrome(string s, int k) {
   int left = 0, right = k - 1, min_replacements = 0;
   while (right < s.length()) {
      int i = left, j = right;
      while (i < j) {
         if (s[i] != s[j])
            min_replacements++;
         i++;
         j--;
      }
      left++;
      right++;
   }
   return min_replacements;
}

int main() {
   string input_string = "abcxyzuvw"; // Replace this with your desired input string
   int k = 3; // Replace this with the desired value of K
   int result = minReplacementsForPalindrome(input_string, k);
   cout << "Minimum replacements required: " << result << endl;
   return 0;
}

Sortie

Minimum replacements required: 7

Conclusion

Cet article explore le problème du nombre minimum de caractères pour convertir une chaîne donnée en une sous-chaîne palindrome de longueur K. Il étudie deux méthodes de base pour résoudre ce problème : la méthode de la force brute et la méthode de la fenêtre glissante. Les méthodes par force brute consistent à vérifier toutes les sous-chaînes possibles de longueur K dans une chaîne donnée, à déterminer si ce sont des palindromes et à vérifier les substitutions nécessaires. Cependant, cette approche est très complexe et est inefficace pour les grandes chaînes.

D'autre part, l'approche de la fenêtre glissante optimise cette méthode en conservant une fenêtre de taille fixe et en mettant à jour efficacement la fenêtre lors de la navigation dans la chaîne d'entrée. Cet article fournit des tests de code et une expérience pour aider les utilisateurs à mieux comprendre et résoudre des problèmes de traitement de chaînes similaires.

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!