GESP 题解库 / 3 级题解 / [GESP202409 三级] 回文拼接 · 第 12 / 28 题
GESP202409 三级 · B4039 · 简单

回文拼接

判断每个字符串能否切成两个回文串,且两段的长度都至少为 2。

📊
n ≤ 10
字符串个数
🔤
长度 ≤ 100
字符串长度
⚡
O(L²)
时间复杂度
🎯
枚举切分点
核心算法
01
题目拆解
把题目拆成一块块,看清全貌

📝 题目原文

一个字符串是回文串,当且仅当它从前往后读和从后往前读完全一样,例如 aabaa、ccddcc 是回文串,abcd 不是。

给定 n 个仅含小写字母的字符串,请判断每个字符串是否由两个长度至少为 2 的回文串前后拼接而成。是则输出 Yes,否则输出 No。

💡
人话翻译:在原串上找一个"切分点",把字符串切成左右两段;要求左段是回文、右段也是回文,并且两段长度都 ≥ 2。切分点可以有很多个,只要有一个满足就输出 Yes。

🔍 关键词提取

回文判断枚举切分点子串长度约束双指针

已知条件

项目说明
输入第一行 n;随后 n 行每行一个小写字母串
输出每行一个 Yes 或 No
数据范围1 ≤ n ≤ 10,字符串长度 ≤ 100
长度约束两段长度都必须至少为 2

需要解决的问题

02
思维导图
整理解题思路的全貌
✂️ 枚举切分点 + 判两段回文
📥 读入
n 个字符串
逐个独立判断
串长 L ≤ 100
L < 4 直接 No
✂️ 枚举切分
左段长度 i 从 2 开始
i 最大到 L − 2
保证右段也 ≥ 2
两段都要判
🔍 判回文
双指针 i、j 向中间夹
或反转后比较
O(段长)
两段都真才 Yes
⚠️ 易错点
漏掉长度 ≥ 2 的约束
整串回文误判为 Yes
i 的取值范围写错
L < 4 时无解
03
样例手算推导
把样例 4 个串逐个试切

🧮 样例逐串验证

样例答案依次是 No、Yes、No、No。我们把每个串的所有切分点都试一遍。

1
abcd(长度 4)

L = 4,左段长度只能取 i = 2

左段 "ab":a 与 b 不同 → 不是回文

❌ 唯一切分点失败 → No

2
aabbb(长度 5)

i = 2:左段 "aa" 是回文 ✅,右段 "bbb" 是回文 ✅

两段长度分别是 2 和 3,都 ≥ 2 ✅

✅ 找到合法切分 → Yes

3
aaac(长度 4)

L = 4,只能取 i = 2

左段 "aa" 是回文 ✅,右段 "ac":a 与 c 不同 ❌

❌ 切分点失败 → No

4
abcdd(长度 5)

i = 2:左段 "ab" 不是回文 ❌

i = 3:左段 "abc" 不是回文 ❌

❌ 所有切分点都失败 → No

📊 逐个切分点检查表

字符串长度尝试的 i左段右段结论
abcd42ab ❌cd ❌No
aabbb52aa ✅bbb ✅Yes
aabbb53aab ❌bb ✅(已找到,无需再试)
aaac42aa ✅ac ❌No
abcdd52ab ❌cdd ❌No
abcdd53abc ❌dd ✅No
🔑
注意 aabbb 的 i = 3 那行:左段 "aab" 不是回文,但右段 "bb" 是回文 —— 必须两段同时满足才算成功。只要找到一个 i 让两段都成立就可以立刻输出 Yes。
04
解法对比
枚举切分点 vs 只查边界

⚔️ 解法对比

🟢 枚举所有切分点(推荐) 推荐

i 从 2 到 L−2,每轮判断两段是否回文

  • 时间 O(L²)
  • L ≤ 100,最多试 98 个切分点
  • 逻辑直白不易错
  • 找到即可提前退出
💡
为什么不用更聪明的做法:本题 n ≤ 10、L ≤ 100,规模极小,枚举足够快。把时间花在"写对"上更划算。

🟠 只检查长度与两端字符

试图用"首尾相同"之类的必要条件快速判断

  • 必要条件不能当充分条件
  • "ab...ba" 也不一定两段都是回文
  • 容易漏解
  • 反而更慢(还要额外验证)
⚠️
结论:回文性质没有简单的边界判据,老老实实枚举切分点 + 双指针判断最稳。

📈 性能对比

方案运算量(L=100)正确性
枚举切分点约 10⁴ 次字符比较✅ 完全正确
边界启发式不确定❌ 可能漏解
05
算法流程图
外层枚举切分点、内层双指针判回文
开始读入 n读入一个字符串 s,L = s.size()L ≥ 4 吗?是 ✓继续枚举切分点否 ✗直接输出 Noi 从 2 枚举到 L − 2,两段都判回文存在某个 i 使两段都是回文吗?是 ✓输出 Yes否 ✗输出 Non 个字符串都判完了吗?结束还有字符串 → 继续判断
← 左右滑动查看完整流程图
06
动手算一算
自己输入数据试试看

✂️ 回文拼接检测器

每行输入一个字符串,程序会枚举所有切分点并标出哪些能成功。

结果会显示在这里

点按钮开始 →

07
代码精讲
逐段拆解,彻底搞懂

💻 完整 C++ 代码

#include <bits/stdc++.h>
using namespace std;

// 判断 s 的 [l, r] 闭区间是否为回文
bool isPal(const string &s, int l, int r) {
    while (l < r) {
        if (s[l] != s[r]) return false;
        l++; r--;
    }
    return true;
}

int main() {
    int n;
    scanf("%d", &n);
    while (n--) {
        string s;
        cin >> s;
        int L = (int)s.size();

        bool ok = false;
        // 左段长度为 i,则右段长度为 L - i,两者都必须 >= 2
        for (int i = 2; i <= L - 2; i++) {
            if (isPal(s, 0, i - 1) && isPal(s, i, L - 1)) {
                ok = true;
                break;
            }
        }
        printf("%s\n", ok ? "Yes" : "No");
    }
    return 0;
}
🔑
循环上界为什么是 L − 2?左段长度是 i,右段长度是 L − i。要求左段 ≥ 2 → i ≥ 2;要求右段 ≥ 2 → L − i ≥ 2 → i ≤ L − 2。两个条件合起来就是 2 ≤ i ≤ L − 2。如果写成 i ≤ L − 1,右段可能只剩 1 个字符,就会误判。

📖 关键几行怎么看

代码作用为什么这样写
isPal(s, l, r)闭区间判回文双指针从两端向中间夹,O(段长)
for (i = 2; i <= L - 2; i++)枚举左段长度同时保证两段长度都 ≥ 2
isPal(s,0,i-1) && isPal(s,i,L-1)两段都要是回文必须同时成立,用的是 &&
break提前退出找到一个合法切分就能定 Yes
⚠️
三个坑:① 把整串是否是回文当成答案 —— 题目要求切成两段,即使整串回文(如 "abba")也可能不满足;② 忘记长度 ≥ 2 的约束,把 "aaa" 切成 "a"+"aa" 判成 Yes(实际应判 No);③ 循环写成 i < L,导致右段可能为空。
08
边界测试 & 易错点
把坑都踩一遍,考试不翻车

🧪 边界测试用例表

写完程序后,用这些数据自查一遍:

输入答案考察点
abcdNo题面样例
aabbbYes题面样例:aa + bbb
aaacNo左段回文但右段不是
abcddNo题面样例
aaaNo长度 3 无解(切成 a+aa 有段长为 1)
abbaNo整串是回文,但切不出两段回文
aaaaYesaa + aa
aabbYesaa + bb
✅
自查清单:① 切分范围是 2 ~ L−2 吗?② 两段都用 && 连接吗?③ 长度 < 4 的串直接输出 No 吗?

🚨 易错点清单

⚠️
把整串回文当答案:abba 整串是回文,但要切成两段("ab"+"ba" 或 "abb"+"a")都不满足,答案应是 No。
⚠️
漏掉长度 ≥ 2:aaa 切成 "a"+"aa" 两段都是回文,但左段长度只有 1,不合法。
⚠️
循环上界写错:必须是 i ≤ L − 2,写成 i ≤ L − 1 会让右段为空串(空串也算回文,造成误判)。
⚠️
n 组数据忘了重置 ok:ok 要写在每组循环内部。
09
复杂度分析
算算效率怎么样

📊 复杂度四宫格

时间复杂度
O(n × L²)
空间复杂度
O(L)
L 最大
100
最坏运算
约 10⁵

时间怎么算的?

空间都用在哪?

只需要字符串本身,双指针判断不需要额外空间。

✅ 最坏 10 万次字符比较,任何语言都是瞬间完成。

10
知识拓展
学一道题,会一类题

🔗 常用技巧小抄

// 判断子串 [l, r] 是否回文(双指针)
bool isPal(const string &s, int l, int r) {
    while (l < r && s[l] == s[r]) { l++; r--; }
    return l >= r;
}

// 判断整个字符串是否回文(两种写法)
bool isPal1(const string &s) { return isPal(s, 0, (int)s.size() - 1); }
bool isPal2(string s) { string t = s; reverse(t.begin(), t.end()); return s == t; }

// 枚举所有切分点的通用骨架
for (int i = 1; i < (int)s.size(); i++) {
    string left  = s.substr(0, i);
    string right = s.substr(i);
    // 对 left、right 做判断
}

🌟 举一反三

把这道题用到的基本功拆出来,它们能迁移到很多同类问题上。

能力点本题怎么用还能迁移到
回文双指针两端向中间夹回文子串、回文判断类题目
枚举切分点s.substr(0,i) 与 s.substr(i)字符串拆分、区间划分类题目
区间参数化把 [l, r] 作为函数参数避免反复创建子串,写法更高效
🌟
思考题:如果题目改成"切成三段回文串",该怎么做?(提示:两层枚举切分点 i、j,复杂度升到 O(L³);L ≤ 100 时约 10⁶ 次,仍然可行。)