La plus petite sous-chaîne qui doit être supprimée pour faire de la chaîne donnée un palindrome

Un palindrome est une séquence de caractères qui se lit de la même manière dans le sens avant et arrière. En informatique et en programmation, les palindromes sont un thème courant dans les problèmes de manipulation de chaînes. Dans cet article, nous allons explorer comment trouver la sous-chaîne de taille minimale qui doit être supprimée d'une chaîne donnée pour en faire un palindrome. Nous fournirons une solution C++ bien structurée et inclurons un exemple pour illustrer les cas de test.

Énoncé du problème

Étant donné une chaîne 's' de longueur 'n', nous devons trouver la taille minimale de la sous-chaîne qui doit être supprimée pour que la chaîne restante devienne un palindrome.

Algorithme

• Créez une fonction appelée isPalindrome qui prend la chaîne 's' comme paramètre et renvoie vrai s'il s'agit d'un palindrome, sinon elle renvoie faux.

• Créez une fonction appelée minSizeSubstringToRemove qui prend la chaîne 's' comme paramètre.

• Initialisez la variable 'minSize' à la longueur de la chaîne.

• Parcourez la chaîne à l'aide d'une boucle, en incrémentant un index « i » de 0 à « n ».

• Dans chaque itération, effectuez les étapes suivantes −

• Créez deux sous-chaînes depuis le début de la chaîne jusqu'à l'index 'i' et une autre depuis l'index 'i' jusqu'à la fin de la chaîne.

• Vérifiez si l'une des sous-chaînes est un palindrome.

• Si une sous-chaîne est un palindrome, mettez à jour 'minSize' à la valeur minimale entre la longueur de la sous-chaîne non palindrome et 'minSize'.

• Renvoyer 'minSize' comme résultat.

Exemple

#include <iostream>
#include <string>
#include <algorithm>

// Function to check if a string is a palindrome
bool isPalindrome(const std::string &s) {
   int left = 0;
   int right = s.length() - 1;
   
   while (left < right) {
      if (s[left] != s[right]) {
         return false;
      }
      ++left;
      --right;
   }
   
   return true;
}

// Function to find the minimum size substring to be removed
int minSizeSubstringToRemove(std::string s) {
   int n = s.length();
   int minSize = n;
   
   for (int i = 0; i <= n; ++i) {
      std::string leftSubstring = s.substr(0, i);
      std::string rightSubstring = s.substr(i, n - i);
   
      if (isPalindrome(leftSubstring)) {
         minSize = std::min(minSize, static_cast<int>(rightSubstring.length()));
      }
      if (isPalindrome(rightSubstring)) {
         minSize = std::min(minSize, static_cast<int>(leftSubstring.length()));
      }
   }
   
   return minSize;
}

int main() {
   std::string s = "abccbaab";
   int result = minSizeSubstringToRemove(s);
   std::cout << "Minimum size substring to be removed: " << result << std::endl;
   
   return 0;
}

Sortie

Minimum size substring to be removed: 2

Exemple de cas de test

Considérez la chaîne suivante : "abccbaab". Les sous-chaînes possibles et leurs états palindromiques correspondants sont les suivants :

• Sous-chaîne gauche = "", sous-chaîne droite = "abccbaab", palindrome = false

• Sous-chaîne gauche = "a", sous-chaîne droite = "bccbaab", palindrome = false

• Sous-chaîne gauche = "ab", sous-chaîne droite = "ccbaab", palindrome = false

• Sous-chaîne gauche = "abc", sous-chaîne droite = "cbaab", palindrome = false

• Sous-chaîne gauche = "abcc", sous-chaîne droite = "baab", palindrome = false

• Sous-chaîne gauche = "abccb", sous-chaîne droite = "aab", palindrome = true (sous-chaîne gauche)

• Sous-chaîne gauche = "abccba", sous-chaîne droite = "ab", palindrome = true (sous-chaîne gauche)

• Sous-chaîne gauche = "abccbaa", sous-chaîne droite = "b", palindrome = false

• Sous-chaîne gauche = "abccbaab", sous-chaîne droite = "", palindrome = false

D'après l'itération ci-dessus, nous pouvons voir que la taille minimale de la sous-chaîne à supprimer est de 2, ce qui se produit lorsque la sous-chaîne de gauche est "abccba" et la sous-chaîne de droite est "ab". Dans ce cas, supprimer la sous-chaîne droite "ab" fera de la chaîne restante "abccba" un palindrome.

Conclusion

Dans cet article, nous explorons le problème de la recherche de la sous-chaîne de taille minimale qui doit être supprimée pour faire d'une chaîne donnée un palindrome. Nous fournissons une implémentation C++ claire et efficace qui utilise une simple boucle pour parcourir une chaîne, créer des sous-chaînes et vérifier leur état de palindrome pour trouver la taille minimale de la sous-chaîne qui doit être supprimée.

En comprenant cet algorithme, vous pouvez appliquer des concepts similaires à la résolution d'autres problèmes de manipulation de chaînes et de palindrome en informatique et en programmation.

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!