[GESP202403四级]相似字符串

阅读量: 48 编辑

22、相似字符串

对于两个字符串A和B,如果A可以通过删除⼀个字符,或插入⼀个字符,或修改⼀个字符变成B,那么我们说A和B是相似的。

⽐如 apple 可以通过插入⼀个字符变成 applee ,可以通过删除⼀个字符变成 appe ,也可以通过修改⼀个字符变成 bpple ,因此 apple 和 applee 、 appe 、 bpple 都是相似的。但 applee 并不能通过任意⼀个操作变成bpple ,因此它们并不相似。

特别地,完全相同的两个字符串也是相似的。给定T组A,B,请你分别判断他们是否相似。

【输入描述】

第⼀行⼀个正整数T。

接下来T行,每行两个用空格隔开的字符串A和B。

保证T<=100,A, B的长度不超过 50。保证A和B只包含字写字母。

【输出描述】

输出T行,对于每组A,B,如果它们相似,则输出 similar ,否则输出 not similar 。

【特别提醒】

在常规程序中,输入、输出时提供提示是好习惯。但在本场考试中,由于系统限定,请不要在输入、输出中附带任何提示信息。

【样例输入】

5	
apple	applee
apple	appe
apple	bpple
applee 	bpple 
apple	 apple

【样例输出】

similar
similar
similar	
not similar
similar

【参考程序】

// 爱码岛编程
#include <bits/stdc++.h>
using namespace std;

bool isSimilar(string A, string B) {

    //设定A是比较长的
    if (A.size() < B.size()) {
        swap(A, B);
    }
	
    if (A.size() - B.size() > 1) {
        return false;
    }

    int diff = 0;
    if (A.size() == B.size()) {
        for (int i = 0; i < A.size(); i++) {
            if (A[i] != B[i]) {
                diff++;
            }
        }
        return diff <= 1;
    } else {
        int i = 0, j = 0;
        while (i < A.size() && j < B.size()) {
            if (A[i++] != B[j++]) {
                i++;
                diff++;
            }
        }
        return diff <= 1;
    }
}

int main() {

    int T;
    cin >> T;

    string A, B;
    while (T--) {
        cin >> A >> B;
        if (isSimilar(A, B)) {
            cout << "similar" << endl;
        } else {
            cout << "not similar" << endl;
        }
    }

    return 0;
}
爱码岛编程公众号
试卷资料
爱码岛编程小程序
在线刷题
苏ICP备13052010号
©2023 南京匠成信息科技有限公司