1 算法题 ：判断一个字符串是否是回文（正读和反读都一样）
1.1 题目含义
判断一个字符串是否是回文（Palindrome），意味着判断这个字符串是否可以从前往后读和从后往前读都是相同的。一个回文字符串忽略标点符号、空格和大小写，只关注字符的排列顺序。例如，单词 “level” 和 “madam” 都是回文，因为它们的字符序列在正向和反向读取时都是相同的。
1.2 示例
示例 1:
输入: “level”
输出: true
解释: “level” 是一个回文字符串，因为 “level” 正着读和反着读都是 “level”。
示例 2:
输入: “race a car”
输出: false
解释: “race a car” 不是一个回文字符串，因为 “race a car” 反转后变成 “rac a ecar”，这两者不相同。
示例 3:
输入: “A man, a plan, a canal: Panama”
输出: true
解释: 忽略标点符号和空格后，“amanaplanacanalpanama” 是一个回文字符串，因为它正着读和反着读都是相同的。
2 解题思路
解题思路如下：
（1）预处理字符串：
首先，将输入的字符串转换为小写（或大写），以便忽略大小写差异。
然后，移除字符串中的所有非字母字符，如空格、标点符号等。这一步是为了确保只关注字母字符的排列顺序。
（2）比较字符串与反转字符串：
接下来，将预处理后的字符串与其反转字符串进行比较。
如果两个字符串相同，则原字符串是回文；如果不同，则不是回文。
（3）实现比较：
一种简单的方法是使用两个指针，一个从字符串的开始位置遍历，另一个从字符串的末尾位置遍历。
比较两个指针所指向的字符是否相同，如果相同则继续移动指针，直到两个指针相遇或发现不同的字符。
如果在相遇之前发现不同的字符，则字符串不是回文；如果两个指针相遇，则字符串是回文。
（4）优化：
如果字符串长度是奇数，并且中间字符是回文中心，则只需要比较除去中间字符后的字符串的对称部分。
如果字符串长度是偶数，则直接比较对称位置的字符。
（5）返回结果：
根据比较的结果，返回相应的布尔值（true 或 false），表示字符串是否是回文。
3 算法实现代码
3.1 字符串副本比对
如下为算法实现代码：
#include <string>
#include <cctype>
#include <algorithm>
class Solution
{
public:
bool isPalindrome(const std::string& str) {
// 预处理字符串：转换为小写并移除非字母字符
std::string preprocessedStr;
for (char c : str) {
if (std::isalpha(c)) {
preprocessedStr.push_back(std::tolower(c));
}
}
// 比较预处理后的字符串与其反转字符串
std::string reversedStr = preprocessedStr;
std::reverse(reversedStr.begin(), reversedStr.end());
// 如果两个字符串相同，则是回文
return preprocessedStr == reversedStr;
}
};
这段代码首先定义了一个 Solution 类，并在其中实现了一个名为 isPalindrome 的成员函数。isPalindrome 函数接受一个字符串引用作为参数，并返回一个布尔值来指示该字符串是否是回文。
在 isPalindrome 函数中，首先对字符串进行预处理，将其转换为小写并移除所有非字母字符。这通过遍历原始字符串 str 并使用 std::isalpha 和 std::tolower 函数完成。
接下来创建一个名为 preprocessedStr 的字符串，用于存储预处理后的结果。如果当前字符是字母，则将其转换为小写并添加到 preprocessedStr 中。
然后创建 reversedStr 字符串，它是 preprocessedStr 的反转。使用 std::reverse 函数可以轻松实现字符串的反转。
最后比较 preprocessedStr 和 reversedStr 是否相同。如果相同，则原字符串是回文，函数返回 true；否则，返回 false。
这样就可以通过创建Solution类的实例并调用 isPalindrome 方法来检查任何给定字符串是否是回文了。
3.2 使用指针从两头扫描
使用指针从字符串的两头遍历来检查回文的方法可以避免了创建额外的字符串副本，从而提高了效率：
如下为算法实现代码：
#include <iostream>
#include <cctype>
#include <string>
class Solution
{
public:
bool isPalindrome(const std::string& s) {
// 移除字符串中的非字母字符并转换为小写
std::string processedStr;
for (char c : s) {
if (std::isalpha(c)) {
processedStr.push_back(std::tolower(c));
}
}
// 使用指针从两头遍历字符串
const char* left = processedStr.data();
const char* right = processedStr.data() + processedStr.size() - 1;
while (left < right) {
if (*left != *right) {
return false;
}
left++;
right--;
}
// 如果所有字符都匹配，则字符串是回文
return true;
}
};
在这个实现中，isPalindrome 函数首先处理输入字符串，移除所有非字母字符并将所有字母转换为小写。
然后，它使用两个指针 left 和 right 分别指向处理后的字符串的首尾。
接着，它进入一个循环，在循环中比较 left 和 right 指针所指向的字符，如果不相等，则返回 false 表示字符串不是回文。如果所有字符都匹配，循环结束后返回 true 表示字符串是回文。
4 测试用例
以下是针对上面算法的测试用例：
（1）基本回文测试：
输入：“level”
预期输出：true
解释：这个字符串是一个基本的回文字符串，由相同字符的正向和反向序列组成。
（2）忽略大小写和非字母字符测试：
输入：“A man, a plan, a canal: Panama”
预期输出：true
解释：在忽略大小写和非字母字符后，这个字符串是一个回文。
（3）包含数字和非字母字符测试：
输入：“race123 a car”
预期输出：false
解释：即使移除了非字母字符，剩余的字符序列 “raceacar” 不是回文。
（4）奇数长度回文测试：
输入：“radar”
预期输出：true
解释：这个字符串是一个奇数长度的回文，中间字符 ‘a’ 可以被忽略。
（5）偶数长度回文测试：
输入：“madam”
预期输出：true
解释：这个字符串是一个偶数长度的回文，字符序列在正向和反向读取时相同。
通过这些测试用例，基本可以验证代码是否能正确处理基本回文、大小写和非字母字符的处理、包含数字和非字母字符的情况，以及不同长度（奇数和偶数）的回文字符串。这些测试用例覆盖了算法的主要逻辑和边界条件。