迹忆客 专注技术分享

本文将介绍几种在 C++ 中使用递归函数检查回文字符串的方法。

使用递归函数检查回文字符串

递归函数是从函数主体中调用自身的函数。递归方法不是实现回文校验算法的最佳方法。isPalindrome 函数接受三个参数，并返回一个布尔值，以指示所传递的 string 是否是回文。第二个和第三个参数用于存储字符串序列的开始和结束位置。作为第一个条件，我们评估字符串长度是否为 1，如果是，则函数立即返回一个肯定值。接下来，比较第一个和最后一个字符，如果不相等，则该函数返回 false。否则，执行将继续检查字符串是否在当前 st 和 en 位置的中间包含更多字符。如果条件评估为真，则使用移位的位置和相同的字符串值进行递归调用。另一方面，错误条件会强制函数返回 true。

#include <iostream>
#include <string>

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

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::cout; using std::endl;
using std::string; using std::cin;
using std::equal; using std::remove;

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::cout; using std::endl;
using std::string; using std::cin;
using std::equal; using std::remove;

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