判断两个字符串是否能通过增、删、改恰好一个字符(或零个)变成对方。
如果 A 能通过删除一个字符、插入一个字符或修改一个字符变成 B,则称 A 和 B 是相似的。两个完全相同的字符串也是相似的。
给定 T 组 A、B,分别判断是否相似。相似输出 similar,否则输出 not similar。
编辑距离分类讨论双指针长度差
| 项目 | 说明 |
|---|---|
| 输入 | 第一行 T;随后 T 行每行两个字符串 A、B |
| 输出 | 每行 similar 或 not similar |
| 数据范围 | T ≤ 100 |
| 长度 | A、B 长度不超过 50,仅含小写字母 |
| 允许操作 | 删 1 个、插 1 个、改 1 个(任选其一),或什么都不做 |
样例答案:similar / similar / similar / not similar / similar。
长度:5 与 6,差为 1 → 属于"插入/删除"情况
短的是 apple,长的是 applee
检查:长串 applee 删掉最后一个 e → apple ✅
(也可以用双指针:前 5 个字符全同,长串多出 1 个字符)
✅ similar
长度:5 与 4,差为 1
长串 apple 删掉 'l' → appe ✅
✅ similar
长度都是 5,差为 0 → 属于"修改"情况
逐位比较:a/b 不同,其余 p、p、l、e 全同
只有 1 个位置不同 → 修改 1 个字符即可 ✅
✅ similar
长度:6 与 5,差为 1 → "插入/删除"情况
短串 bpple,长串 applee
检查长串删一个字符能否变短串:
删 a → pplee ✗;删第一个 p → aplee ✗;删第二个 p → aplee ✗
删 l → appe e→ appee ✗;删 e → apple ✗;删最后的 e → apple ✗
没有任何一种删除能得到 bpple ✗
❌ not similar
完全相同 → 题目特别说明也属于相似
✅ similar
| 长度关系 | 对应操作 | 判定方法 |
|---|---|---|
| 差 > 1 | 不可能 | 直接 not similar |
| 差 = 0 | 修改(或不变) | 不同位置个数 ≤ 1 |
| 差 = 1 | 插入 / 删除 | 长串删一格后余下与短串完全相同 |
a 和 b 就完全不同。所以判定"长度差 = 1"时,还要验证去掉那一个字符后,剩下的部分逐位相同,不能只靠长度差下结论。用双指针可以把三种情况写得很统一,我们看它的原理。
i、j 分别指向 A、B 的开头
只要 A[i] == B[j] 就让两个指针都前进
停下来时,i、j 就指向第一个不同的位置
定位到第一个差异点
长度相等:两边都跳过这一格,继续比较剩余部分
A 更长:只让 i 前进一格(相当于在 A 里删掉这个字符)
B 更长:只让 j 前进一格
统一成"跳过一格后必须完全一致"
如果一路比到最后都没遇到不同:
长度相等 → 完全相同 → similar
长度差 1 → 长串末尾多一个 → similar
长度差 > 1 → not similar
✅ 所有情况都覆盖了
双指针写法只有 15 行左右,且不易漏情况
找第一个不同位置,再按长度关系跳一格后验证
if 长度差 > 1 / == 0 / == 1 各写一段逻辑
| 方案 | 代码量 | 覆盖情况 |
|---|---|---|
| 双指针 | 约 15 行 | 统一处理 |
| 分类讨论 | 约 40 行 | 三段各管一类 |
每行输入两个字符串(空格分隔),程序会判断它们是否"编辑距离 ≤ 1"。
点按钮开始 →
#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) | 长度相等时验证 | 各跳一格后剩余必须完全一致 |
写完程序后,用这些数据自查一遍:
| 输入 | 答案 | 考察点 |
|---|---|---|
apple applee | similar | 长度差 1,插入/删除即可 |
apple appe | similar | 长度差 1,删掉 l |
apple bpple | similar | 同长度,只差 1 个字符 |
applee bpple | not similar | 题面样例:长度差 1 但内容差异不止一个字符 |
apple apple | similar | 完全相同也相似 |
a b | similar | 长度相等且都只差 1 个字符 |
ab abcde | not similar | 长度差 3 > 1 |
substr 会产生临时字符串,但长度极小。
✅ 规模极小,任何写法都瞬间完成。这题考的是"分类是否想全",不是效率。
// "编辑距离 <= 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 算法 |
dp[i][j] 表示 A 的前 i 个字符变成 B 的前 j 个字符所需的最少操作数,最终判断 dp[|A|][|B|] ≤ k。本题是 k = 1 的特例,所以可以走捷径。)