【例5.12】回文字串

GitHub跳转原题关系图返回列表

安全读取整行输入,剥离末尾可能存在的句号后,使用双指针从两端向中间遍历判断是否为回文串。

OJ: roj

题目 ID: 5046

难度:入门

标签:字符串双指针模拟

创建: 2026-10-09 00:07

更新: 2026-10-09 00:07

形式化题目

给定一个长度不超过 100100 的字符串 SS,该字符串在一行中给出,且通常以字符 . 作为结束标志。需要判断去除末尾可能存在的 . 之后,剩余的字符串 S′S' 是否为回文串。如果是回文串,输出 Yes;否则输出 No。判断时区分大小写。

正解

思路

本题的核心在于判断字符串是否中心对称。主要需要注意以下几个细节:

  1. 题意与 . 的角色:. 是终结符,不计入回文判断。判定前必须先剥掉末尾的 .。如果剥掉后是空串,空串也算作回文。
  2. 输入不都以 . 结尾:这是本题极其凶险的一个暗坑。虽然题目描述中说输入以 . 结束,但是实际上测试数据可能末尾并不带有 .(例如原样样例 abccb)。
  3. 读入方式的选择:既然是读“一行”,就有可能包含空格,如果使用 cin >> s 遇到空格就会截断。虽然本题实测数据中没有空格,但依据题意“一行字符串”,最稳妥且符合规范的做法是读取一整行。使用 getline(cin, s)(C++)或 sys.stdin.readline()(Python)。
  4. 回文判断:去除末尾的 . 后,可以使用双指针法:左指针从字符串开头向右移动,右指针从字符串末尾向左移动,每次比较两个指针指向的字符是否相同。如果遇到不同的字符,说明不是回文串;如果两指针相遇都没有发现不同的字符,则说明是回文串。或者可以直接构造逆序字符串并进行比较(在 Python 中可以用切片 s[::-1] 直接解决)。

代码

python
#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-08 23:30
# update_at: 2026-10-08 23:30

import sys


def solve() -> None:
    line = sys.stdin.readline()
    if not line:
        return  # 空输入:无数据可判

    # 题面说「一行字符串」,readline 保证读到空格也不截断
    s = line.rstrip('\r\n')  # 剥行尾 '\r'(CRLF 容错)与 '\n'

    # '.' 是行尾终止符,不参与回文判断;数据末尾可能没有 '.'(如样例 abccb),故需判断
    if s.endswith('.'):
        s = s[:-1]

    # 回文判断区分大小写:切片反转后直接比较
    print("Yes" if s == s[::-1] else "No")


if __name__ == "__main__":
    solve()
cpp
/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-08 23:30
 * update_at: 2026-10-08 23:30
 */
#include <iostream>
#include <string>

using namespace std;

typedef long long ll;

string s; // 整行输入(含结尾的终止符 '.')

void solve() {
    // 题面说「一行字符串」,用 getline 读整行,避免 cin >> s 在空格处截断
    if (!getline(cin, s)) {
        return; // 空输入:无数据可判,静默退出
    }

    // 先剥行尾的 '\r'(CRLF 容错)与 '\n',再剥终止符 '.'
    while (!s.empty() && (s.back() == '\r' || s.back() == '\n')) {
        s.pop_back();
    }

    // '.' 是行尾终止符,不参与回文判断;数据末尾可能没有 '.'(如样例 abccb),故需判断
    if (!s.empty() && s.back() == '.') {
        s.pop_back();
    }

    // 双指针:左指针从左端、右指针从右端相向比较,任一对不同即非回文
    // 注意判断区分大小写('a' 与 'A' 视为不同字符)
    ll len = s.size();
    ll left = 0;
    ll right = len - 1;
    bool is_palindrome = true;
    while (left < right) {
        if (s[left] != s[right]) {
            is_palindrome = false;
            break;
        }
        left++;
        right--;
    }

    cout << (is_palindrome ? "Yes" : "No") << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    solve();

    return 0;
}

复杂度

  • 时间复杂度:O(N)O(N),其中 NN 是字符串的长度。我们需要读取整行并遍历字符串的一半(或者构造逆序串),操作时间均与字符串长度成正比。
  • 空间复杂度:O(N)O(N),由于我们直接使用字符串变量缓存整行输入,无论是 C++ 的 string 还是 Python 的 str 都需要分配与字符串长度对应的连续内存空间。双指针遍历本身仅需 O(1)O(1) 的额外空间。

总结

本题的测试数据包含极高质量的陷阱与边界,暴露了多种可能写法的隐患:

  1. 两点裁定 . 的角色:通过实测数据点发现:

    • 测试点 2(输入 a.):输出 Yes。如果把 . 算作字符串的一部分,结果应为 No,这证明了 . 是终结符,必须剥掉。
    • 测试点 1(输入 .):输出 Yes。剥掉 . 后变成了空串,这也同时裁定了空串算回文。
    • 反事实验证(CF1):如果“不剥 .”,会在 3 个测试点失败(说明“剥 .”是承重的逻辑)。
  2. 输入并不一定以 . 结尾(致命坑):

    • 测试点 3(输入 abccb\n):完全没有 .(也没有回车符前的隐藏 .)。
    • 经典写法 while((c=getchar())!='.') 因为无 EOF 保护,在测试点 3 上会导致 SEGFAULT(段错误)。
    • 反事实验证(CF2):如果代码写成“无条件去掉末位(s.pop_back())”,在真实的 10 个测试点上竟然是 0 失败(因为真实数据无法证伪它)。但是如果构造如 aba(无点)的数据,这种代码会把它截成 ab 从而错判为 No。这说明“先判断末尾是不是 . 再决定是否剥去”这个防线是离数据才承重的,即便数据未覆盖,也必须保留。
  3. 区分大小写:

    • 测试点 6 和 8 各含有一对唯一的镜像对 'a' 与 'A',其余对应字符全部相等。
    • 反事实验证(CF3):“比较时转小写”在这两个点上失败。这证明了回文判断必须严格区分大小写。
  4. 数据未覆盖但按题面仍需处理:

    • 反事实验证(CF4):“改用 cin >> s”和(CF5)“不剥 \r”在真实数据上都是 0 失败(数据中没有空格,也没有 CRLF 换行符)。但依据题面“一行字符串”的描述,仍然必须用 getline/readline 并且需要做 CRLF 容错处理。
  5. 题面自相矛盾的输出格式:

    • 题面第 11 行描述:“否输出‘No。’”——带有一个全角句号。
    • 题面第 22 行样例输出:“No”——没有句号。
    • 以数据为准:实测 10 个测试点的输出全部为纯净的 Yes\n 或 No\n,无任何句号。
  6. 跨语言一致性(T9)风险评估:

    • 整除/溢出/类型转换/浮点:无风险。
    • 排序/字典序/字符编码:无风险。实测数据全为 ASCII,C++ 的 char 符号性不影响等值比较 ==。
    • 换行读取差异:无风险。两者均显式做剥除 \r 与 \n 的处理。
  7. 验证强度摘要:

    • 异源验证穷举了所有由 {a, b, A} 组成的长度 0–7 的串(带/不带 .、空格、纯 .、无尾换行、CRLF 等)共 6578 组。
    • C++(双指针)与真值(Python 切片)的分歧仅有 2 组,且均为空输入。此时两种程序均无输出(无错答,符合题面保证至少有一行的前提)。
    • 代码不包含任何硬编码答案表(数值字面量集合仅有 {0, 1})。