GESP202403四级：相似字符串判定规则与代码实现全解析

```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)。 ######[AI问答 | 525点数解答 | 2025-12-22 20:32:06]