GESP 题解库 / 4 级题解 / [GESP202403 四级] 相似字符串 · 第 15 / 25 题
GESP202403 四级 · B3958 · 简单

相似字符串

判断两个字符串是否能通过增、删、改恰好一个字符(或零个)变成对方。

📊
T ≤ 100
测试组数
🔤
长度 ≤ 50
字符串长度
⚡
O(总长度)
时间复杂度
🎯
分类讨论 + 双指针
核心算法
01
题目拆解
把题目拆成一块块,看清全貌

📝 题目原文

如果 A 能通过删除一个字符、插入一个字符或修改一个字符变成 B,则称 A 和 B 是相似的。两个完全相同的字符串也是相似的。

给定 T 组 A、B,分别判断是否相似。相似输出 similar,否则输出 not similar。

💡
人话翻译:这是经典的"编辑距离 ≤ 1"问题。核心思路是按长度差分三种情况讨论:
① 长度差 > 1 → 一定不相似;
② 长度差 = 1 → 看长串删掉一个字符能否变成短串;
③ 长度相等 → 数一数有几个位置不同(≤ 1 才相似)。

🔍 关键词提取

编辑距离分类讨论双指针长度差

已知条件

项目说明
输入第一行 T;随后 T 行每行两个字符串 A、B
输出每行 similar 或 not similar
数据范围T ≤ 100
长度A、B 长度不超过 50,仅含小写字母
允许操作删 1 个、插 1 个、改 1 个(任选其一),或什么都不做

需要解决的问题

02
思维导图
整理解题思路的全貌
🔍 长度差分类 + 双指针
📏 先看长度差
差 > 1 → 直接 not similar
差 = 0 → 数不同位置
差 = 1 → 短串须是长串删一个
只有这三种情况
🔍 双指针
i、j 从 0 开始同步前进
跳过所有相同字符
停在第一个不同处
统计不同个数或跳过一格
✅ 判定
差 0:不同位置 ≤ 1
差 1:跳过长串一格后余下全同
完全相同:similar
任一不满足 → not similar
⚠️ 易错点
忘了"完全相同也相似"
只看长度不看内容
差 1 时跳错串
多个不同位置只跳一次
03
样例手算推导
样例 5 组逐个判定

🧮 样例 5 组逐组分析

样例答案:similar / similar / similar / not similar / similar。

1
第 1 组:apple 与 applee

长度:5 与 6,差为 1 → 属于"插入/删除"情况

短的是 apple,长的是 applee

检查:长串 applee 删掉最后一个 e → apple ✅

(也可以用双指针:前 5 个字符全同,长串多出 1 个字符)

✅ similar

2
第 2 组:apple 与 appe

长度:5 与 4,差为 1

长串 apple 删掉 'l' → appe ✅

✅ similar

3
第 3 组:apple 与 bpple

长度都是 5,差为 0 → 属于"修改"情况

逐位比较:a/b 不同,其余 p、p、l、e 全同

只有 1 个位置不同 → 修改 1 个字符即可 ✅

✅ similar

4
第 4 组:applee 与 bpple

长度:6 与 5,差为 1 → "插入/删除"情况

短串 bpple,长串 applee

检查长串删一个字符能否变短串:

删 a → pplee ✗;删第一个 p → aplee ✗;删第二个 p → aplee ✗

删 l → appe e→ appee ✗;删 e → apple ✗;删最后的 e → apple ✗

没有任何一种删除能得到 bpple ✗

❌ not similar

5
第 5 组:apple 与 apple

完全相同 → 题目特别说明也属于相似

✅ similar

📊 判定规则速查

长度关系对应操作判定方法
差 > 1不可能直接 not similar
差 = 0修改(或不变)不同位置个数 ≤ 1
差 = 1插入 / 删除长串删一格后余下与短串完全相同
🔑
第 4 组为什么失败?因为长度差虽然是 1,但差别不只是"多一个字符"——开头 a 和 b 就完全不同。所以判定"长度差 = 1"时,还要验证去掉那一个字符后,剩下的部分逐位相同,不能只靠长度差下结论。

🧮 双指针的统一处理法

用双指针可以把三种情况写得很统一,我们看它的原理。

1
指针同步前进

i、j 分别指向 A、B 的开头

只要 A[i] == B[j] 就让两个指针都前进

停下来时,i、j 就指向第一个不同的位置

定位到第一个差异点

2
根据长度差决定"跳过谁"

长度相等:两边都跳过这一格,继续比较剩余部分

A 更长:只让 i 前进一格(相当于在 A 里删掉这个字符)

B 更长:只让 j 前进一格

统一成"跳过一格后必须完全一致"

3
特殊情况

如果一路比到最后都没遇到不同:

长度相等 → 完全相同 → similar

长度差 1 → 长串末尾多一个 → similar

长度差 > 1 → not similar

✅ 所有情况都覆盖了

双指针写法只有 15 行左右,且不易漏情况

04
解法对比
分类讨论 vs 双指针统一处理

⚔️ 解法对比

🟢 双指针统一处理(推荐) 推荐

找第一个不同位置,再按长度关系跳一格后验证

  • 时间 O(|A| + |B|)
  • 代码 15 行
  • 三种情况合并处理
  • 不易漏边界
💡
实现要点:先各自跳过相同前缀,然后"按长度差跳一格"(相等时两边都跳),最后检查剩余部分是否完全相同。

🟠 分三种情况分别写

if 长度差 > 1 / == 0 / == 1 各写一段逻辑

  • 代码更长(约 40 行)
  • 每段都要单独处理边界
  • 三种情况容易漏
  • 但思路更贴近题面
⚠️
两种都能过:本题长度 ≤ 50、T ≤ 100,规模极小。分类讨论的写法更好理解,双指针的写法更简洁——建议两种都掌握,考场上选顺手的。

📈 性能对比

方案代码量覆盖情况
双指针约 15 行统一处理
分类讨论约 40 行三段各管一类
05
算法流程图
判长度差 → 双指针找差异 → 验证
开始读入 A、B;长度差 d = |len(A) − len(B)|d > 1 吗?是 ✓输出 not similar否 ✗继续双指针 i、j 同步前进,跳过所有相同的字符d == 0 吗?是 ✓两边各跳一格否 ✗只让较长串跳一格剩余部分完全相同吗?是 ✓输出 similar否 ✗输出 not similar结束还有测试组 → 继续
← 左右滑动查看完整流程图
06
动手算一算
自己输入数据试试看

🔍 字符串相似判定器

每行输入两个字符串(空格分隔),程序会判断它们是否"编辑距离 ≤ 1"。

结果会显示在这里

点按钮开始 →

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

💻 完整 C++ 代码

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

bool similar(const string &a, const string &b) {
    int la = a.size(), lb = b.size();

    // 长度差超过 1,任何单次操作都做不到
    if (abs(la - lb) > 1) return false;

    // 双指针跳过相同的前缀
    int i = 0, j = 0;
    while (i < la && j < lb && a[i] == b[j]) { i++; j++; }

    // 一路相同到底
    if (i == la && j == lb) return true;          // 完全相同

    if (la == lb) {
        // 长度相等:两边各跳过一个字符,再比较剩余部分
        return a.substr(i + 1) == b.substr(j + 1);
    } else if (la > lb) {
        // A 更长:在 A 中删掉当前这个字符
        return a.substr(i + 1) == b.substr(j);
    } else {
        // B 更长:在 B 中删掉当前这个字符
        return a.substr(i) == b.substr(j + 1);
    }
}

int main() {
    int T;
    scanf("%d", &T);
    while (T--) {
        string a, b;
        cin >> a >> b;
        printf("%s\n", similar(a, b) ? "similar" : "not similar");
    }
    return 0;
}
🔑
为什么用 substr 比继续移动指针更简单?因为我们只需要验证"跳过一个字符之后,剩余部分是否完全相同"。substr(i+1) 直接取出后缀,用 == 一次比较完——比自己写循环比较更短、更不容易出错。

📖 关键几行怎么看

代码作用为什么这样写
if (abs(la - lb) > 1) return false;长度粗判一次操作最多改变 1 个字符长度
while (i < la && j < lb && a[i] == b[j])跳过相同前缀定位到第一个不同位置
if (i == la && j == lb) return true;完全相同题目说明这种情况也属于相似
a.substr(i + 1) == b.substr(j + 1)长度相等时验证各跳一格后剩余必须完全一致
⚠️
三个坑:① 忘了"完全相同也算相似"(会漏掉最后一组样例);② 长度差 = 1 时不验证剩余部分,只看长度就判 similar(第 4 组样例会错);③ 长度相等时只跳一边的字符(应该两边都跳)。
08
边界测试 & 易错点
把坑都踩一遍,考试不翻车

🧪 边界测试用例表

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

输入答案考察点
apple appleesimilar长度差 1,插入/删除即可
apple appesimilar长度差 1,删掉 l
apple bpplesimilar同长度,只差 1 个字符
applee bpplenot similar题面样例:长度差 1 但内容差异不止一个字符
apple applesimilar完全相同也相似
a bsimilar长度相等且都只差 1 个字符
ab abcdenot similar长度差 3 > 1
✅
自查清单:① 长度差 > 1 直接返回了吗?② 完全相同的情况处理了吗?③ 长度相等时两边都跳了吗?

🚨 易错点清单

⚠️
忘记"完全相同":题目明确说"两个完全相同的字符串也是相似的"。
⚠️
只判长度差不验证内容:长度差为 1 还必须验证"删掉一个字符后剩余完全相同"。
⚠️
长度相等时跳错边:应该两边各跳一格,然后比较剩余部分。
09
复杂度分析
算算效率怎么样

📊 复杂度四宫格

时间复杂度
O(|A| + |B|)
空间复杂度
O(|A| + |B|)
长度最大
50
T 最大
100

时间怎么算的?

空间都用在哪?

substr 会产生临时字符串,但长度极小。

✅ 规模极小,任何写法都瞬间完成。这题考的是"分类是否想全",不是效率。

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

🔗 常用技巧小抄

// "编辑距离 <= 1" 的三种等价描述
// 1) 能通过删除/插入/修改 一个字符变成对方
// 2) 长度差 <= 1 且最多有一处"错位"
// 3) 最长公共前缀 + 最长公共后缀 覆盖了较短的整个串

// 用前缀/后缀描述(另一角度,也很好写)
bool similar2(const string &a, const string &b) {
    int la = a.size(), lb = b.size();
    if (abs(la - lb) > 1) return false;
    // 最长公共前缀
    int pre = 0;
    while (pre < la && pre < lb && a[pre] == b[pre]) pre++;
    // 最长公共后缀
    int suf = 0;
    while (suf < la - pre && suf < lb - pre
           && a[la - 1 - suf] == b[lb - 1 - suf]) suf++;
    // 中间剩下的差异长度必须 <= 1(长度相等时 <= 2,对应修改一个字符)
    int midA = la - pre - suf, midB = lb - pre - suf;
    return midA <= 1 && midB <= 1;
}

🌟 举一反三

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

能力点本题怎么用还能迁移到
编辑距离最少操作次数拼写纠错、模糊匹配、DNA 比对
分类讨论按长度差分支所有"最多改一处"的判定题
最长公共前缀/后缀前后夹逼描述差异字符串相似度、diff 算法
🌟
思考题:如果题目把"一个字符"放宽到"k 个字符",该怎么改?(提示:这就不再是简单的分类讨论了,需要用动态规划求编辑距离(Levenshtein 距离),状态 dp[i][j] 表示 A 的前 i 个字符变成 B 的前 j 个字符所需的最少操作数,最终判断 dp[|A|][|B|] ≤ k。本题是 k = 1 的特例,所以可以走捷径。)