C++ 字符串回文判断

所谓的 “回文”，简单来说就是一个字符串从左往右正着读，和从右往左反着读完全一样。比如 "level"、"noon"、"abba" 都属于回文字符串，而 "hello" 反过来是 "olleh"，就不是回文字符串。

在 C++ 中，如果我们想判断一个 string 字符串是否为回文，一般分为 2 种实现思路：一种是使用首尾两个下标向中间逐对比较，另一种是先把字符串反转一份再和原字符串对比。

首尾双下标比较法（推荐）

仔细观察回文字符串的特点可以发现，它真正要求的是 “左右两端对称位置上的字符完全相同”。也就是说，第 1 个字符要等于倒数第 1 个字符，第 2 个字符要等于倒数第 2 个字符，后面的字符以此类推。

因此，我们不需要把整个字符串反转过来，只需准备两个下标变量 left 和 right。一开始让 left 指向最左边的首字符（下标为 0），让 right 指向最右边的尾字符（下标为长度减 1），然后一轮一轮往中间靠拢比较。

在算法练习中，这种左右夹逼的做法常被称为 “双指针法”。不过小伙伴们要注意，这里的 “指针” 指的是字符串的下标位置，并不是 char* 内存指针。下面拿长度为 5 的字符串 "level"（下标范围为 0~4）来看看每一轮 left 和 right 的比较过程：

第 1 轮：left = 0, right = 4 -> 比较 'l' 和 'l'
第 2 轮：left = 1, right = 3 -> 比较 'e' 和 'e'
结束时：left = 2, right = 2

如果在向中间靠拢的过程中，我们发现任意一对字符不相等，就能立刻断定它不是回文，直接返回 false 结束判断。下面我们配合 while 循环来实现这个过程。

示例 1：首尾双下标判断回文

#include <iostream>
#include <string>

// 使用首尾双下标判断回文字符串
bool isPalindrome(const std::string& str) {
    int len = str.length();
    int left = 0;            // 左下标指向首字符
    int right = len - 1;     // 右下标指向尾字符

    while (left < right) {
        if (str[left] != str[right]) {
            return false;    // 字符不同则不是回文
        }
        left++;              // 左下标右移一位
        right--;             // 右下标左移一位
    }
    return true;             // 对称位置均相同
}

int main() {
    std::cout << "level: " << (isPalindrome("level") ? "是回文" : "不是回文") << '\n';
    std::cout << "noon: " << (isPalindrome("noon") ? "是回文" : "不是回文") << '\n';
    std::cout << "hello: " << (isPalindrome("hello") ? "是回文" : "不是回文") << '\n';
    return 0;
}

运行结果如下。

level: 是回文
noon: 是回文
hello: 不是回文

分析：

在这个例子中，isPalindrome() 函数先调用 length() 获取字符个数并存入 int 变量 len，从而算出尾字符下标 right = len - 1（先存入有符号 int 可避免空串 "" 计算无符号减 1 时回绕越界）。

随后的 while (left < right) 表示只要左下标还在右下标的左边，我们就继续往中间靠拢比较。一旦发现 str[left] != str[right]，说明左右对称位置的字符不同，函数便立刻返回 false。

可能有些小伙伴会问：“字符串长度是奇数还是偶数，会影响循环退出的条件吗？” 其实 left < right 同时兼顾了这两种情况。当长度为奇数（如 "level"）时，left 和 right 最终会在正中间的下标 2 处相遇，此时 2 < 2 不成立，循环直接退出并返回 true。

当长度为偶数（如 "noon"）时，比完中间相邻的下标 1 和 2 后，left 变成 2、right 变成 1。此时左右下标发生交错，循环同样正常退出。至于单字符 "a" 或空字符串 ""，从一开始就不满足 left < right，程序会直接跳过循环返回 true，同样符合回文的定义。

反转字符串比较法

除了使用首尾双下标，很多小伙伴看到 “正着读和反着读一样” 时，第一反应往往是：先把字符串反转过来，再看它和原来的字符串是否相等。

我们可以引入 <algorithm> 头文件，借助里面的 std::reverse() 函数来实现这个思路。下面我们来看具体代码。

示例 2：反转副本判断回文

#include <algorithm>                         // 提供 std::reverse()
#include <iostream>
#include <string>

// 通过反转副本判断回文字符串
bool isPalindrome(const std::string& str) {
    std::string rev = str;                   // 复制原字符串
    std::reverse(rev.begin(), rev.end());    // 反转副本
    return str == rev;                       // 比较是否相等
}

int main() {
    std::cout << "abba: " << (isPalindrome("abba") ? "是回文" : "不是回文") << '\n';
    std::cout << "lvye: " << (isPalindrome("lvye") ? "是回文" : "不是回文") << '\n';
    return 0;
}

运行结果如下。

abba: 是回文
lvye: 不是回文

分析：

std::string rev = str; 表示先将原字符串完整复制一份保存到变量 rev 中。由于 std::reverse() 会直接修改传入的字符串，而形参 str 带有 const 只读修饰，我们不能直接改动 str 本身。因此这里先对副本 rev 执行反转，最后再通过 str == rev 返回比较结果。

对比上面两种实现方式，反转副本法只有短短 3 行代码，写起来最省事，但需要额外申请内存复制整个字符串并完整反转一遍。而首尾双下标法直接在原字符串上比较，既不用复制副本，遇到不同的字符还能提前退出，因此在实际开发中我们更推荐使用首尾双下标法。