在 C++ 中用递归函数检查回文字符串

Jinku Hu 2023年1月30日 2021年4月29日
  1. 使用递归函数检查回文字符串
  2. 使用 std::equal 算法检查回文字符串
在 C++ 中用递归函数检查回文字符串

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

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

递归函数是从函数主体中调用自身的函数。递归方法不是实现回文校验算法的最佳方法。isPalindrome 函数接受三个参数,并返回一个布尔值,以指示所传递的 string 是否是回文。第二个和第三个参数用于存储字符串序列的开始和结束位置。作为第一个条件,我们评估字符串长度是否为 1,如果是,则函数立即返回一个肯定值。接下来,比较第一个和最后一个字符,如果不相等,则该函数返回 false。否则,执行将继续检查字符串是否在当前 sten 位置的中间包含更多字符。如果条件评估为真,则使用移位的位置和相同的字符串值进行递归调用。另一方面,错误条件会强制函数返回 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 类具有迭代器接口,我们可以使用 beginrbegin 函数指定其范围。不过请注意,以下 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
Author: Jinku Hu
Jinku Hu avatar Jinku Hu avatar

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

相关文章 - C++ String