Der kleinste Teilstring, der entfernt werden muss, um aus dem gegebenen String ein Palindrom zu machen

Ein Palindrom ist eine Zeichenfolge, die sich in Vorwärts- und Rückwärtsrichtung gleich liest. In der Informatik und Programmierung sind Palindrome ein häufiges Thema bei String-Manipulationsproblemen. In diesem Artikel untersuchen wir, wie man die Teilzeichenfolge mit der Mindestgröße findet, die aus einer bestimmten Zeichenfolge entfernt werden muss, um daraus ein Palindrom zu machen. Wir stellen eine gut strukturierte C++-Lösung bereit und fügen ein Beispiel zur Veranschaulichung der Testfälle bei.

Problemstellung

Angesichts einer Zeichenfolge „s“ der Länge „n“ müssen wir die Mindestgröße der Teilzeichenfolge ermitteln, die entfernt werden sollte, damit die verbleibende Zeichenfolge zu einem Palindrom wird.

Algorithmus

• Erstellen Sie eine Funktion namens isPalindrome, die die Zeichenfolge „s“ als Parameter verwendet und „true“ zurückgibt, wenn es sich um ein Palindrom handelt, andernfalls „false“.

• Erstellen Sie eine Funktion namens minSizeSubstringToRemove, die die Zeichenfolge „s“ als Parameter akzeptiert.

• Initialisieren Sie die Variable „minSize“ auf die Länge der Zeichenfolge.

• Durchlaufen Sie die Zeichenfolge mithilfe einer Schleife und erhöhen Sie dabei einen Index „i“ von 0 auf „n“.

• Führen Sie in jeder Iteration die folgenden Schritte aus: −

• Erstellen Sie zwei Teilzeichenfolgen vom Anfang der Zeichenfolge bis zum Index „i“ und eine weitere vom Index „i“ bis zum Ende der Zeichenfolge.

• Überprüfen Sie, ob einer der Teilstrings ein Palindrom ist.

• Wenn es sich bei einem Teilstring um ein Palindrom handelt, aktualisieren Sie „minSize“ auf den Mindestwert zwischen der Länge des Nicht-Palindrom-Teilstrings und „minSize“.

• Gib 'minSize' als Ergebnis zurück.

Beispiel

#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;
}

Ausgabe

Minimum size substring to be removed: 2

Testfallbeispiel

Betrachten Sie die folgende Zeichenfolge: „abccbaab“. Die möglichen Teilzeichenfolgen und ihre entsprechenden palindromischen Zustände sind wie folgt:

• Linker Teilstring = „“, rechter Teilstring = „abccbaab“, Palindrom = false

• Linker Teilstring = „a“, rechter Teilstring = „bccbaab“, Palindrom = false

• Linker Teilstring = „ab“, rechter Teilstring = „ccbaab“, Palindrom = false

• Linker Teilstring = „abc“, rechter Teilstring = „cbaab“, Palindrom = false

• Linker Teilstring = „abcc“, rechter Teilstring = „baab“, Palindrom = false

• Linker Teilstring = „abccb“, rechter Teilstring = „aab“, Palindrom = true (linker Teilstring)

• Linker Teilstring = „abccba“, rechter Teilstring = „ab“, Palindrom = wahr (linker Teilstring)

• Linker Teilstring = „abccbaa“, rechter Teilstring = „b“, Palindrom = false

• Linker Teilstring = „abccbaab“, rechter Teilstring = „“, Palindrom = false

Aus der obigen Iteration können wir ersehen, dass die Mindestgröße der zu löschenden Teilzeichenfolge 2 beträgt, was auftritt, wenn die linke Teilzeichenfolge „abccba“ und die rechte Teilzeichenfolge „ab“ ist. In diesem Fall wird durch das Löschen der rechten Teilzeichenfolge „ab“ die verbleibende Zeichenfolge „abccba“ zu einem Palindrom.

Fazit

In diesem Artikel untersuchen wir das Problem, die Teilzeichenfolge mit der Mindestgröße zu finden, die entfernt werden muss, um eine bestimmte Zeichenfolge in ein Palindrom zu verwandeln. Wir bieten eine klare und effiziente C++-Implementierung, die eine einfache Schleife verwendet, um einen String zu durchlaufen, Teilstrings zu erstellen und ihren Palindromstatus zu überprüfen, um die Mindestgröße des Teilstrings zu ermitteln, der entfernt werden muss.

Wenn Sie diesen Algorithmus verstehen, können Sie ähnliche Konzepte zur Lösung anderer String-Manipulations- und Palindrom-Probleme in der Informatik und Programmierung anwenden.

Das obige ist der detaillierte Inhalt vonDer kleinste Teilstring, der entfernt werden muss, um aus dem gegebenen String ein Palindrom zu machen. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!