C++ 第20题：字符串回文检测（双指针双向逼近与空间 O(1) 判定）

题目

编写程序，检测给定的字符串是否为回文字符串（Palindrome）。要求忽略所有非字母和非数字的标点空格，且对大小写不敏感（例如："A man, a plan, a canal: Panama" 应被判定为合法回文）。采用双指针从两端向中间对向收敛逼近，算法额外空间复杂度严格为 O(1)，无需额外申请临时拷贝串。

输入格式：一行可能包含大小写、空格与标点符号的文本。

输出格式：输出该文本是否为合法回文串的布尔判定结果。

数据范围与约定：文本长度 <code>≤ 10^5</code>，纯 ASCII 字符。

思路与算法

1. 双指针 O(1) 空间优势
初学者常使用 std::reverse 构造新串再比对，消耗 O(N) 堆内存。左右双指针（left 与 right）就地向中心扫描，遇到非字母数字字符则单侧跳过，完全零额外内存。

2. 标准库字符分类
使用 std::isalnum(static_cast<unsigned char>(c)) 过滤有效字符；使用 std::tolower 统一字符规范。

3. 指针越界交叉防御
在 while 循环跳过标点时，内层循环必须始终加上 left < right 条件限制，防止在全标点极端输入下两个指针交叉越界产生越界访问。

完整程序

#include <iostream>
#include <string>
#include <cctype>

bool isPalindrome(const std::string& s) {
    if (s.empty()) return true;

    int left = 0;
    int right = static_cast<int>(s.size()) - 1;

    while (left < right) {
        // 1. 左指针向右寻找下一个字母数字
        while (left < right && !std::isalnum(static_cast<unsigned char>(s[left]))) {
            ++left;
        }
        // 2. 右指针向左寻找上一个字母数字
        while (left < right && !std::isalnum(static_cast<unsigned char>(s[right]))) {
            --right;
        }

        // 3. 统一转小写比对
        if (std::tolower(static_cast<unsigned char>(s[left])) != 
            std::tolower(static_cast<unsigned char>(s[right]))) {
            return false;
        }

        ++left;
        --right;
    }

    return true;
}

int main() {
    std::string line;
    if (!std::getline(std::cin, line)) {
        return 0;
    }

    bool res = isPalindrome(line);
    std::cout << "测试文本: [\"" << line << "\"]\n";
    std::cout << "回文检测结论: " << (res ? "【是回文字符串】" : "【不是回文字符串】") << "\n";

    return 0;
}

运行示例

示例 1：

输入：

A man, a plan, a canal: Panama

输出：

测试文本: ["A man, a plan, a canal: Panama"]
回文检测结论: 【是回文字符串】

示例 2：

输入：

race a car

输出：

测试文本: ["race a car"]
回文检测结论: 【不是回文字符串】