[GESP202403 四级] 相似字符串 题目描述 对于两个字符串 � A 和 � B，如果 � A 可以通过删除一个字符，或插入一个字符，或修改一个字符变成 � B，那么我们说 � A 和 � B 是相似的。 比如 apple 可以通过插入一个字符变成 applee，可以通过删除一个字符变成 appe，也可以通过修改一个字符变成 bpple。因此 apple 和 applee、 appe、 bpple 都是相似的。但 applee 并不能 通过任意一个操作变成 bpple，因此它们并不相似。 特别地，两个完全相同的字符串也是相似的。 给定 � T 组 � , � A,B，请你分别判断它们是否相似。 输入格式 第一行一个正整数 � T。 接下来 � T 行，每行两个用空格隔开的字符串 � A 和 � B。 输出格式 对组 � , � A,B，如果他们相似，输出 similar，否则输出 not similar。 样例 #1 样例输入 #1 5 apple applee apple appe apple bpple applee bpple a

```cpp #include <iostream> #include <string> #include <cmath> using namespace std; bool isSimilar(string A, string B) { int lenA = A.length(); int lenB = B.length(); // 长度差超过1，不可能相似 if (abs(lenA - lenB) > 1) return false; // 完全相同的字符串是相似的 if (A == B) return true; // 长度相等的情况：只能通过修改一个字符 if (lenA == lenB) { int diffCount = 0; for (int i = 0; i < lenA; i++) { if (A[i] != B[i]) { diffCount++; if (diffCount > 1) return false; } } return diffCount == 1; } // 长度相差1的情况：只能通过插入或删除一个字符 // 确保A是较短的字符串 if (lenA > lenB) { swap(A, B); swap(lenA, lenB); } int i = 0, j = 0; int diffCount = 0; while (i < lenA && j < lenB) { if (A[i] == B[j]) { i++; j++; } else { diffCount++; if (diffCount > 1) return false; j++; // 跳过B中不同的字符（相当于在A中插入或在B中删除） } } return true; } int main() { int T; cin >> T; while (T--) { string A, B; cin >> A >> B; if (isSimilar(A, B)) { cout << "similar" << endl; } else { cout << "not similar" << endl; } } return 0; } ``` 解题思路： 1. 长度检查：两个字符串长度差超过1，直接判定不相似。 2. 完全相同：两个字符串完全相同，判定相似。 3. 长度相等：只能通过修改一个字符，检查不同字符数量是否为1。 4. 长度差1：只能通过插入或删除一个字符，使用双指针遍历，允许一次不匹配。 时间复杂度：O(n)，n为字符串长度。 空间复杂度：O(1)。 [2025-12-22 20:32:06 | AI问答 | 525点数解答]