判断每个字符串能否切成两个回文串,且两段的长度都至少为 2。
一个字符串是回文串,当且仅当它从前往后读和从后往前读完全一样,例如 aabaa、ccddcc 是回文串,abcd 不是。
给定 n 个仅含小写字母的字符串,请判断每个字符串是否由两个长度至少为 2 的回文串前后拼接而成。是则输出 Yes,否则输出 No。
回文判断枚举切分点子串长度约束双指针
| 项目 | 说明 |
|---|---|
| 输入 | 第一行 n;随后 n 行每行一个小写字母串 |
| 输出 | 每行一个 Yes 或 No |
| 数据范围 | 1 ≤ n ≤ 10,字符串长度 ≤ 100 |
| 长度约束 | 两段长度都必须至少为 2 |
样例答案依次是 No、Yes、No、No。我们把每个串的所有切分点都试一遍。
L = 4,左段长度只能取 i = 2
左段 "ab":a 与 b 不同 → 不是回文
❌ 唯一切分点失败 → No
i = 2:左段 "aa" 是回文 ✅,右段 "bbb" 是回文 ✅
两段长度分别是 2 和 3,都 ≥ 2 ✅
✅ 找到合法切分 → Yes
L = 4,只能取 i = 2
左段 "aa" 是回文 ✅,右段 "ac":a 与 c 不同 ❌
❌ 切分点失败 → No
i = 2:左段 "ab" 不是回文 ❌
i = 3:左段 "abc" 不是回文 ❌
❌ 所有切分点都失败 → No
| 字符串 | 长度 | 尝试的 i | 左段 | 右段 | 结论 |
|---|---|---|---|---|---|
| abcd | 4 | 2 | ab ❌ | cd ❌ | No |
| aabbb | 5 | 2 | aa ✅ | bbb ✅ | Yes |
| aabbb | 5 | 3 | aab ❌ | bb ✅ | (已找到,无需再试) |
| aaac | 4 | 2 | aa ✅ | ac ❌ | No |
| abcdd | 5 | 2 | ab ❌ | cdd ❌ | No |
| abcdd | 5 | 3 | abc ❌ | dd ✅ | No |
i 从 2 到 L−2,每轮判断两段是否回文
试图用"首尾相同"之类的必要条件快速判断
| 方案 | 运算量(L=100) | 正确性 |
|---|---|---|
| 枚举切分点 | 约 10⁴ 次字符比较 | ✅ 完全正确 |
| 边界启发式 | 不确定 | ❌ 可能漏解 |
每行输入一个字符串,程序会枚举所有切分点并标出哪些能成功。
点按钮开始 →
#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; }
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 |
i < L,导致右段可能为空。写完程序后,用这些数据自查一遍:
| 输入 | 答案 | 考察点 |
|---|---|---|
abcd | No | 题面样例 |
aabbb | Yes | 题面样例:aa + bbb |
aaac | No | 左段回文但右段不是 |
abcdd | No | 题面样例 |
aaa | No | 长度 3 无解(切成 a+aa 有段长为 1) |
abba | No | 整串是回文,但切不出两段回文 |
aaaa | Yes | aa + aa |
aabb | Yes | aa + bb |
i ≤ L − 2,写成 i ≤ L − 1 会让右段为空串(空串也算回文,造成误判)。ok 要写在每组循环内部。只需要字符串本身,双指针判断不需要额外空间。
✅ 最坏 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] 作为函数参数 | 避免反复创建子串,写法更高效 |