中 · 双指针

回文串

你已经会从后往前遍历来反转字符串了。现在试试同时从两端往中间走 —— 并且一旦发现不匹配就立刻停:一个反例就够了。

一句话答案从两端各放一个下标往中间走，中途没有对不上就输出 yes —— 单词全是小写且不含空格，不需要额外规范化。

题目

输入: 一行,一个由小写字母组成的单词,最长 100 个字符,不含空格。

输出: 正反读一样输出 yes,否则输出 no。

样例:

输入输出
racecaryes
hellono
ayes

单个字符当然是回文,「没有可比较的字符」也是。所以这题里循环条件比循环体更重要。

你的解答

main.cpp — 你的解答
「运行我的输入」用的自定义输入

判题在浏览器本地运行。死循环会在 3 秒后被自动中断 —— 但还是确保每个循环都有出口。代码随打随存。

卡住了？提示

提示 1 — 笨办法是两趟,你只需要一趟

你可以复制一份、反转、再比较 —— 那是 O(n) 时间和 O(n) 额外空间。但回文是对称的,所以可以原地检查:第 0 个对第 n−1 个,第 1 个对第 n−2 个,依此类推。不用复制。

提示 2 — 两个下标,一个条件

int i = 0, j = n - 1; 然后 while (i < j)。比较 s[i] 和 s[j];不匹配就置标志并 break,否则 i++、j--。i < j 这个条件正是奇数长度单词能正确工作的原因 —— 中间那个字符是和自己比,本来也一定相等。

提示 3 — 那个会咬人的差一

下标 i 的镜像位置是 n - 1 - i,不是 n - i。写错了,你就是在拿每个字符和它右边相邻的字符比 —— 而且还多读了一个字节,那个字节恰好是结束符 '\0',于是答案静默地变错,而不是崩溃。

题解（先自己试试！） 
#include <iostream>
#include <cstring>
using namespace std;

int main() {
    char s[105];
    cin >> s;
    int n = strlen(s);

    int i = 0, j = n - 1;
    bool ok = true;
    while (i < j) {
        if (s[i] != s[j]) {
            ok = false;
            break;
        }
        i++;
        j--;
    }

    if (ok) cout << "yes" << endl;
    else cout << "no" << endl;
    return 0;
}

两个下标相向收缩,是很多技巧的共同形状:判断数组是否有序、原地去重、在有序数组里找一对和为目标值的数、以及快排的分区。它成立的原因永远是同一个 —— 数据有对称性,而双指针让你在不占额外内存的前提下利用它。接下来把「看结构而不是看顺序」这个思路搬到网格上:矩阵转置。

深度解析

为什么这样做对

两个下标从两端相向走,每一步比较一对镜像字符。字符串本身有对称性,双指针就是利用它、同时不占额外内存的方式。

代价

O(n) 时间、O(1) 空间,而且发现第一个不匹配就 break。复制一份反转再比较也是 O(n),但要多 O(n) 空间去存一份你根本不需要的副本。

常见错法

  • 镜像位置写成 n - i 而不是 n - 1 - i:拿每个字符和它右邻居比,还多读一个字节 —— 那个字节恰好是 '\0' 结束符,于是答案静默变错,而不是崩溃。
  • 写成 i <= j 不会错但没意义:中间那个字符会和自己比一次。写成 i < n 更糟 —— 每一对都比较了两遍。

下一步

同一个思路换个形状 —— 看网格的结构而不是顺序:矩阵转置。

记住这两句

  • 两个下标相向走,一步比一对。
  • i 的镜像位置是 n - 1 - i,不是 n - i。
🐞 这段是错的 —— 点开,亲手让它挂一次

镜像位置写成 n - i —— 拿每个字符和它右边那个比

#include <iostream>
#include <cstring>
using namespace std;

int main() {
    char s[105];
    cin >> s;
    int n = strlen(s);
    bool ok = true;
    for (int i = 0; i < n / 2; i++) {
        if (s[i] != s[n - i]) ok = false;
    }
    if (ok) cout << "yes" << endl;
    else cout << "no" << endl;
    return 0;
}