Prüfen auf eine palindrome Zeichenkette mit einer rekursiven Funktion in C++

1. Verwenden Sie die rekursive Funktion, um nach einem Palindrom-String zu suchen
2. Verwendung des std::equal-Algorithmus zur Prüfung auf eine Palindrom-Zeichenkette

In diesem Artikel werden verschiedene Methoden zum Überprüfen eines Palindrom-Strings mit einer rekursiven Funktion in C++ erläutert.

Verwenden Sie die rekursive Funktion, um nach einem Palindrom-String zu suchen

Eine rekursive Funktion ist diejenige, die sich vom Funktionskörper aus aufruft. Eine rekursive Methode ist nicht der optimale Weg, um einen Palindrom-Überprüfungsalgorithmus zu implementieren. Die Funktion isPalindrome akzeptiert drei Argumente und gibt einen booleschen Wert zurück, um anzugeben, ob die übergebene Zeichenkette ein Palindrom ist. Das zweite und dritte Argument werden verwendet, um die Anfangs- und Endpositionen der Zeichenkettenfolge zu speichern. Als erste Bedingung bewerten wir, ob die Zeichenkettenlänge 1 ist, und wenn ja, gibt die Funktion sofort mit einem positiven Wert zurück. Als nächstes werden das erste und das letzte Zeichen verglichen, und wenn sie nicht gleich sind, gibt die Funktion false zurück. Andernfalls prüft die Ausführung weiterhin, ob die Zeichenkette mehr Zeichen in der Mitte der aktuellen Positionen st und en enthält. Wenn die Bedingung true ergibt, wird der rekursive Aufruf mit verschobenen Positionen und demselben Zeichenkettenwert ausgeführt. Andererseits zwingt eine falsche Bedingung die Funktion, true zurückzugeben.

#include <iostream>
#include <string>

using std::cin;
using std::cout;
using std::endl;
using std::equal;
using std::remove;
using std::string;

bool isPalindrome(const string &s, size_t st, size_t en) {
  if (s.length() == 1) return true;

  if (s[st] != s[en - 1]) return false;

  if (st < en + 1) return isPalindrome(s, st + 1, en - 1);

  return true;
}

int main() {
  string s1 = "radar";
  string s2 = "Was it a cat I saw";

  isPalindrome(s1, 0, s1.length()) ? cout << "s1 is a palindrome" << endl
                                   : cout << "s1 is not a palindrome" << endl;

  isPalindrome(s2, 0, s2.length()) ? cout << "s2 is a palindrome" << endl
                                   : cout << "s2 is not a palindrome" << endl;

  return EXIT_SUCCESS;
}

Ausgabe:

s1 is a palindrome
s2 is not a palindrome

Beachten Sie, dass die vorherige Lösung die Palindrome nicht mit Großbuchstaben und Leerzeichen wie dem Objekt s2 identifizieren kann. Wir müssen also die Zeichenkette in die gleichen Groß- und Kleinschreibung konvertieren und Leerzeichen entfernen, um alle gültigen Palindrome korrekt zu finden. Der Algorithmus std::trasform und das Idiom erase-remove werden verwendet, um die Zeichenkette in das kompatible Formular für die Funktion isPalindrome zu analysieren.

#include <iostream>
#include <string>

using std::cin;
using std::cout;
using std::endl;
using std::equal;
using std::remove;
using std::string;

bool isPalindrome(const string &s, size_t st, size_t en) {
  if (s.length() == 1) return true;

  if (s[st] != s[en - 1]) return false;

  if (st < en + 1) return isPalindrome(s, st + 1, en - 1);

  return true;
}

int main() {
  string s2 = "Was it a cat I saw";

  transform(s2.begin(), s2.end(), s2.begin(),
            [](unsigned char c) { return tolower(c); });
  s2.erase(remove(s2.begin(), s2.end(), ' '), s2.end());

  isPalindrome(s2, 0, s2.length()) ? cout << "s2 is a palindrome" << endl
                                   : cout << "s2 is not a palindrome" << endl;

  return EXIT_SUCCESS;
}

Ausgabe:

s2 is a palindrome

Verwendung des std::equal-Algorithmus zur Prüfung auf eine Palindrom-Zeichenkette

std::equal ist Teil der C++ Standard Template Library und kann zum Vergleichen von Bereichen verwendet werden. Da die Klasse string über die Iterator-Schnittstelle verfügt, können wir ihren Bereich mit den Funktionen begin und rbegin angeben. Beachten Sie jedoch, dass die folgende Überladungsversion std::equal drei Argumente enthält, von denen die ersten beiden den ersten Bereich angeben, während das dritte Argument den Beginn des zweiten Bereichs angibt.

#include <iostream>
#include <string>

using std::cin;
using std::cout;
using std::endl;
using std::equal;
using std::remove;
using std::string;

bool checkPalindrome(string& s) {
  string tmp = s;
  transform(tmp.begin(), tmp.end(), tmp.begin(),
            [](unsigned char c) { return tolower(c); });
  tmp.erase(remove(tmp.begin(), tmp.end(), ' '), tmp.end());

  if (equal(tmp.begin(), tmp.begin() + tmp.size() / 2, tmp.rbegin())) {
    return true;
  } else {
    return false;
  }
}

int main() {
  string s1 = "radar";
  string s2 = "Was it a cat I saw";

  checkPalindrome(s2) ? cout << "s2 is a palindrome" << endl
                      : cout << "s2 is not a palindrome" << endl;

  return EXIT_SUCCESS;
}

Ausgabe:

s2 is a palindrome