在 C++ 中用递归函数检查回文字符串
Jinku Hu
2023年10月12日
![在 C++ 中用递归函数检查回文字符串](/img/Cpp/feature-image---palindrome-recursion-in-cpp.webp)
本文将介绍几种在 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