在 C++ 中用递归函数检查回文字符串
Jinku Hu
2023年10月12日
本文将介绍几种在 C++ 中使用递归函数检查回文字符串的方法。
使用递归函数检查回文字符串
递归函数是从函数主体中调用自身的函数。递归方法不是实现回文校验算法的最佳方法。isPalindrome 函数接受三个参数，并返回一个布尔值，以指示所传递的 string 是否是回文。第二个和第三个参数用于存储字符串序列的开始和结束位置。作为第一个条件，我们评估字符串长度是否为 1，如果是，则函数立即返回一个肯定值。接下来，比较第一个和最后一个字符，如果不相等，则该函数返回 false。否则，执行将继续检查字符串是否在当前 st 和 en 位置的中间包含更多字符。如果条件评估为真，则使用移位的位置和相同的字符串值进行递归调用。另一方面，错误条件会强制函数返回 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;
}
输出：
s1 is a palindrome
s2 is not a palindrome
请注意，先前的解决方案无法识别包含大小写字母和空格（例如 s2 对象）的回文。因此，我们需要将字符串转换为相同的大小写字母，并删除所有空格以正确找到所有有效回文。std::trasform 算法和 erase-remove 惯用法用于将字符串解析为 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;
}
输出：
s2 is a palindrome
使用 std::equal 算法检查回文字符串
std::equal 是 C++ 标准模板库的一部分，可用于比较范围。因此，由于 string 类具有迭代器接口，我们可以使用 begin 和 rbegin 函数指定其范围。不过请注意，以下 std::equal 重载版本采用三个参数，其中前两个指定第一个范围，而第三个参数表示第二个范围的开始。
#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;
}
输出：
s2 is a palindrome
作者： Jinku Hu
