C++回文判断与字符串处理技巧

1. 回文判断的C++实现与技巧解析

回文判断是编程入门阶段的经典问题，它考察了字符串处理的基本功。题目要求我们判断输入的字符串（长度小于200）是否是回文。回文是指正读和反读都相同的字符串，比如"madam"、"上海自来水来自海上"等。

1.1 核心算法思路

最直观的回文判断方法是将字符串反转后与原字符串比较。C++标准库提供了reverse函数可以方便地实现字符串反转：

cpp复制#include <iostream>
#include <bits/stdc++.h>
using namespace std;

int main() {
    string s;
    while(getline(cin,s)){
        string s_old = s;  // 保存原始字符串
        reverse(s.begin(),s.end());  // 反转字符串
        if(s == s_old){
            cout<<"Yes"<<endl;
        }else{
            cout<<"No"<<endl;
        }
    }
    return 0;
}

注意：reverse函数是原地操作，会直接修改原字符串，且返回类型为void。因此必须事先保存原字符串的副本，不能写成string s_new = reverse(s.begin(),s.end())，这会导致编译错误。

1.2 性能分析与优化

虽然上述方法简洁明了，但它的时间复杂度是O(n)，空间复杂度也是O(n)（因为需要保存副本）。对于长度小于200的字符串完全够用，但如果处理超长字符串，可以考虑更高效的实现：

cpp复制bool isPalindrome(const string& s) {
    int left = 0, right = s.length()-1;
    while(left < right) {
        if(s[left++] != s[right--]) 
            return false;
    }
    return true;
}

这种双指针方法只需O(1)额外空间，且平均情况下只需比较