Verificare la presenza di una stringa Palindrome con una funzione ricorsiva in C++
- Usa la funzione ricorsiva per verificare la presenza di una stringa palindromo
-
Usa il controllo algoritmo
std::equalper una stringa Palindrome
Questo articolo spiegherà diversi metodi per verificare la presenza di una stringa palindromo con una funzione ricorsiva in C++.
Usa la funzione ricorsiva per verificare la presenza di una stringa palindromo
Una funzione ricorsiva è quella che chiama se stessa dal corpo della funzione. Un metodo ricorsivo non è il modo ottimale per implementare un algoritmo di controllo palindromo. La funzione isPalindrome accetta tre argomenti e restituisce un valore booleano per indicare se la stringa passata è un palindromo. Il secondo e il terzo argomento vengono utilizzati per memorizzare le posizioni di inizio e fine della sequenza di stringhe. Come prima condizione, valutiamo se la lunghezza della stringa è 1 e, in tal caso, la funzione ritorna immediatamente con un valore affermativo. Successivamente, il primo e l’ultimo carattere vengono confrontati e, se non sono uguali, la funzione restituisce false. Altrimenti, l’esecuzione continua a controllare se la stringa contiene più caratteri al centro delle attuali posizioni st e en. Se la condizione è vera, la chiamata ricorsiva viene eseguita con posizioni spostate e lo stesso valore di stringa. D’altra parte, la condizione falsa costringe la funzione a restituire true.
#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;
}
Produzione:
s1 is a palindrome
s2 is not a palindrome
Si noti che la soluzione precedente non può identificare i palindromi con lettere e spazi misti come l’oggetto s2. Quindi, dobbiamo convertire la stringa nelle stesse lettere maiuscole e rimuovere eventuali spazi per trovare correttamente tutti i palindromi validi. L’algoritmo std::trasform e l’idioma cancella-rimuovi sono usati per analizzare la stringa nella forma compatibile per la funzione isPalindrome.
#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;
}
Produzione:
s2 is a palindrome
Usa il controllo algoritmo std::equal per una stringa Palindrome
std::equal fa parte della libreria di modelli standard C++ e può essere utilizzato per confrontare intervalli. Quindi, poiché la classe string ha l’interfaccia dell’iteratore, possiamo specificare il suo intervallo con le funzioni begin e rbegin. Nota però, la seguente versione di overload std::equal accetta tre argomenti, i primi due dei quali specificano il primo intervallo, mentre il terzo argomento denota l’inizio del secondo intervallo.
#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;
}
Produzione:
s2 is a palindrome
Founder of DelftStack.com. Jinku has worked in the robotics and automotive industries for over 8 years. He sharpened his coding skills when he needed to do the automatic testing, data collection from remote servers and report creation from the endurance test. He is from an electrical/electronics engineering background but has expanded his interest to embedded electronics, embedded programming and front-/back-end programming.
LinkedIn Facebook