返回首页 返回题库

相似字符串判断

C++ 简单 GESP四级真题 #字符串#双指针

题目描述

题面描述

对于两个字符串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的长度不超过50。保证A和B只包含小写字母。

输出格式

输出T行,对于每组测试用例A,B,如果两个字符串相似,则输出 similar,否则输出 not similar。

特别提醒

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

样例1

输入:

5
apple applee
apple appe
apple bpple
applee bpple
apple apple

输出:

similar
similar
similar
not similar
similar

数据范围

1 ≤ T ≤ 100,字符串A和B的长度均不超过50,且仅包含小写字母。

时间限制

1秒

内存限制

128MB

💡 查看提示(先自己想一想再看)
核心考察知识点:字符串操作、双指针算法、条件判断。解题思路:1. 首先判断两个字符串长度差,如果超过1直接返回不相似;2. 若长度相等,统计不同字符的数量,最多允许1个不同;3. 若长度差为1,用双指针遍历较短和较长的字符串,最多允许一次跳过较长字符串的字符,其余字符需完全匹配。常见易错点:处理长度不同的字符串时,容易遗漏其中一个字符串末尾的剩余字符,以及双指针移动逻辑错误。
⚙ 开始做这道题 0 人做过 · 0 收藏 · 9 浏览

讨论(0)