Verifique se há uma string de palíndromo com uma função recursiva em C++
- Use a função recursiva para verificar se há uma string de palíndromo
-
Use a verificação de algoritmo
std::equalpara uma string de palíndromo
Este artigo explicará vários métodos de verificação de uma string de palíndromo com uma função recursiva em C++.
Use a função recursiva para verificar se há uma string de palíndromo
Uma função recursiva é aquela que se chama a partir do corpo da função. Um método recursivo não é a maneira ideal de implementar um algoritmo de verificação de palíndromo. A função isPalindrome recebe três argumentos e retorna um valor booleano para indicar se a string passada é um palíndromo. O segundo e o terceiro argumentos são usados para armazenar as posições inicial e final da sequência da string. Como primeira condição, avaliamos se o comprimento da string é 1 e, em caso afirmativo, a função retorna imediatamente com um valor afirmativo. Em seguida, o primeiro e o último caracteres são comparados e, se não forem iguais, a função retorna false. Caso contrário, a execução continua para verificar se a string contém mais caracteres no meio das posições st e en atuais. Se a condição for avaliada como verdadeira, a chamada recursiva será feita com posições trocadas e o mesmo valor de string. Por outro lado, a condição falsa força a função a retornar 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;
}
Resultado:
s1 is a palindrome
s2 is not a palindrome
Observe que a solução anterior não pode identificar os palíndromos com letras maiúsculas e espaços mistos, como o objeto s2. Portanto, precisamos converter a string para as mesmas letras maiúsculas e minúsculas e remover todos os espaços para encontrar todos os palíndromos válidos corretamente. O algoritmo std::trasform e o idioma erase-remove são usados para analisar a string para a forma compatível para a função 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;
}
Resultado:
s2 is a palindrome
Use a verificação de algoritmo std::equal para uma string de palíndromo
std::equal faz parte da C++ Standard Template Library e pode ser utilizado para comparar intervalos. Assim, como a classe string tem a interface iteradora, podemos especificar seu intervalo com as funções begin e rbegin. Observe, porém, que a seguinte versão de sobrecarga std::equal leva três argumentos, os dois primeiros especificando o primeiro intervalo, enquanto o terceiro argumento denota o início do segundo intervalo.
#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;
}
Resultado:
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