相似字符串 题解

题目分析

本题要求判断两个字符串是否相似。“相似”定义为两个字符串可以通过恰好一次下述操作互相转换（或完全相同）：

• 删除一个字符
• 插入一个字符
• 修改一个字符

换句话说，判断的是两个字符串的编辑距离是否为 0 或 1（只能执行一次操作）。

数据范围：$T \le 100$，字符串长度 $\le 50$，完全可以使用 $O(n)$ 的模拟方法轻松通过。

解题思路

我们可以根据两个字符串长度的关系，将情况分为三类：

1. 长度相等

此时只能通过“修改一个字符”或“完全相同”来实现相似。
我们只需逐位比较，统计不同字符的个数 $diff$。

• 若 $diff = 0$ ：两串相同，相似。
• 若 $diff = 1$ ：修改一个字符即可，相似。
• 若 $diff \ge 2$ ：至少需要两次修改，不相似。

2. 长度相差 1

此时只能通过“插入一个字符”或“删除一个字符”实现相似（插入和删除互为逆操作）。
假设较短串为 $S$，较长串为 $L$，我们在 $S$ 中插入一个字符可以得到 $L$。
实现时使用双指针：

• 指针 $i$ 遍历较短串，指针 $j$ 遍历较长串。
• 当 $S[i] = L[j]$ 时，两指针同时后移。
• 当 $S[i] \neq L[j]$ 时，相当于在较短串的当前位置“插入” $L[j]$ 这个字符，只将 $j$ 后移一位（模拟跳过较长串中多出的字符），同时记录一次不同。
• 若不同次数超过 $1$，则不相似；否则相似。

因为长度只差 $1$，若前面完全匹配，最后较长串剩余的一个字符也可视为插入操作。

3. 长度相差大于 1

无论插入、删除还是修改，最多只能改变一个字符的长度，因此长度差大于 $1$ 时一定不相似，可直接返回 false。

算法说明

1. 读入字符串 $A, B$，计算长度差 $|len_A - len_B|$，若大于 $1$ 直接输出 not similar。
2. 若长度相等：遍历计数不同字符，不同数 $\le 1$ 则 similar。
3. 若长度差 $1$：确定较短和较长字符串，使用双指针扫描，跳过次数 $\le 1$ 则 similar。

参考代码

cpp
复制
1#include <iostream>
2#include <string>
3using namespace std;
4
5bool isSimilar(string A, string B) {
6    int m = A.size(), n = B.size();
7    // 长度差大于1，一定不相似
8    if (abs(m - n) > 1) return false;
9
10    // 1. 长度相等：判断是否修改 <= 1 个字符
11    if (m == n) {
12        int diff = 0;
13        for (int i = 0; i < m; ++i) {
14            if (A[i] != B[i]) {
15                if (++diff > 1) return false;
16            }
17        }
18        return diff <= 1;  // diff = 0 或 1
19    } 
20    // 2. 长度差 1：判断是否通过一次插入/删除得到
21    else {
22        // 让 shorter 指向较短的字符串，longer 指向较长的
23        string& shorter = (m < n) ? A : B;
24        string& longer  = (m < n) ? B : A;
25        int i = 0, j = 0, diff = 0;
26        while (i < shorter.size() && j < longer.size()) {
27            if (shorter[i] != longer[j]) {
28                if (++diff > 1) return false;
29                ++j;  // 跳过 longer 多出的字符，相当于在 shorter 插入
30            } else {
31                ++i;
32                ++j;
33            }
34        }
35        return true;  // 长度差1且至多一次跳过，剩余部分自然匹配
36    }
37}
38
39int main() {
40    int T;
41    cin >> T;
42    while (T--) {
43        string A, B;
44        cin >> A >> B;
45        if (isSimilar(A, B))
46            cout << "similar" << endl;
47        else
48            cout << "not similar" << endl;
49    }
50    return 0;
51}

代码解释

• abs(m - n) > 1：快速排除长度差过大的情况。
• 长度相等分支：diff 记录对应位置字符不同的次数，一旦超过 $1$ 立即返回 false。
• 长度差 1 分支：
  • 用引用 shorter 和 longer 避免复制，同时统一处理插入/删除逻辑。
  • i 遍历较短串，j 遍历较长串，遇到相同字符两指针齐动；遇到不同则只移动 j，模拟“在较短串中插入该字符”或“从较长串中删除该字符”，并增加一次不同计数。
  • 因为长度仅差 1，while 结束后即使 i 没走完或 j 没走完，剩余部分必然是恰好一对一的匹配或者仅多一个字符（该情况已在跳过时处理），因此可以直接返回 true。

时间复杂度分析

对于每组数据：

• 若长度相等：只需一次线性扫描，时间复杂度 $O(L)$，$L$ 为字符串长度。
• 若长度差 1：双指针最多遍历较短串加较长串的长度，也是 $O(L)$。
  总时间复杂度为 $O(T \times L)$，在最坏情况下约为 $100 \times 50 = 5000$ 次字符比较，非常高效，能在 1ms 限制内轻松运行。

总结

本题本质上是一道“编辑距离为 1”的判定问题。根据长度关系分类讨论，用简单的双指针和计数即可解决。写代码时注意边界条件和跳过逻辑的正确性即可。