[GESP202403四级] 相似字符串
大约 5 分钟字符串
[GESP202403四级] 相似字符串
【算法标签】 字符串、枚举
【语法标签】 :string、for循环、while循环、函数
对于两个字符串 和 ,如果 可以通过删除一个字符,或插入一个字符,或修改一个字符变成 ,那么我们说 和 是相似的。
比如 apple 可以通过插入一个字符变成 applee ,可以通过删除一个字符变成 appe ,也可以通过修改一个字符变成 bpple ,因此 apple 和 applee 、 appe 、 bpple 都是相似的。但applee 并不能通过任意一个操作变成 bpple ,因此它们并不相似。
特别地,完全相同的两个字符串也是相似的。
给定 组 ,请你分别判断他们是否相似。
第一行一个正整数 。
接下来 行,每行两个用空格隔开的字符串 和 。
保证 , 的长度不超过 50。保证 和 只包含小写字母。
输出格式
输出 行,对于每组 ,如果它们相似,则输出similar ,否则输出 not similar 。
样例 #1
样例输入 #1
5
apple applee
apple appe
apple bpple
applee bpple
apple apple样例输出 #1
similar
similar
similar
not similar
similar来源
GESP 2024年03月 C++四级T1
时间:1s
空间:256M
一、题意简述
两个字符串 A、B 满足以下任意一种情况,即为相似字符串:
- 两字符串长度相等,仅修改至多 1 个字符可互相转换(包含完全相同的情况);
- 两字符串长度差值为 1,较长字符串删除 1 个字符后与短字符串相等(等价于短字符串插入 1 个字符得到长字符串)。
反之则不相似。
数据范围:测试组数 (T \le 100),单个字符串长度 (\le 50),仅包含小写英文字母
二、解题思路
根据题意拆分两种合法场景,分情况判断:
- 场景 1:两字符串长度相等:统计对应位置不同字符的数量,不同字符数 (\le 1) 则相似(对应「修改一个字符」操作,0 个不同即完全相同);
- 场景 2:两字符串长度差恰好为 1:枚举较长字符串的每一个位置,模拟「删除当前位置字符」,若删除后和短字符串完全一致,则相似(对应「插入 / 删除一个字符」操作);
- 其余所有情况(长度差 (\ge 2)),判定为不相似。
优化小技巧:统一将较短字符串放在前面、较长字符串放在后面,简化长度判断逻辑。
三、参考代码
#include <bits/stdc++.h>
using namespace std;
// 两字符串长度相等时:判断至多只有1个字符不同(修改操作)
// cnt == 0 时两串完全相同,也返回 true
bool checkModify(string x, string y){
int cnt = 0;
for(int i = 0; i < x.size(); i++){
if (x[i] != y[i]) cnt++;
}
return cnt <= 1;
}
// 两字符串长度差1:删除长串某一个字符后是否等于短串(增/删操作)
bool checkInsert(string shortStr, string longStr){
// 枚举长串每一个位置,模拟删除该位置字符
for(int i = 0; i < longStr.size(); i++){
string temp;
for(int j = 0; j < longStr.size(); j++){
if(j != i) temp += longStr[j];
}
if(shortStr == temp) return true;
}
return false;
}
int main(){
int t;
cin >> t;
while(t--){
string a, b;
cin >> a >> b;
// 保证 a 是较短字符串,b 是较长字符串
if(a.size() > b.size()) swap(a, b);
bool ok = false;
if(a.size() == b.size()) ok = checkModify(a, b); // 长度相等,判断修改场景
else if(b.size() - a.size() == 1) ok = checkInsert(a, b); // 长度差1,判断增删场景
cout << (ok ? "similar" : "not similar") << "\n";
}
return 0;
}四、代码逐块解析
1. 函数 checkModify
功能:处理长度相等的字符串,校验是否仅需修改至多 1 个字符。
- 遍历字符串所有位置,统计字符不匹配的个数
cnt; cnt == 0说明两串完全相同,也算相似;cnt == 1可通过修改 1 个字符转换,算相似;cnt >= 2无法通过一次修改完成,返回false。
2. 函数 checkInsert
功能:处理长度差为 1的字符串,模拟删除长串单个字符。
- 外层循环:枚举长字符串每一个下标
i,代表要删除的位置; - 内层循环:拼接长字符串,跳过下标 i,得到删除单个字符后的新串
temp; - 若
temp和短字符串相等,说明可通过一次增 / 删转换,返回true; - 全部位置枚举完毕都不匹配,返回
false。
3. 主函数 main
- 读取测试组数 T,循环处理每组数据;
- 读取两个字符串
a、b,通过swap保证a长度 (\le b) 长度; - 按长度关系分两种场景判断:
- 长度相等 → 调用
checkModify(已包含完全相同的情况); - 长度差 1 → 调用
checkInsert; - 其他情况(差值 > 1)→ 直接判定不相似;
- 长度相等 → 调用
- 用一个
bool ok统一记录结果,最后输出。
五、易错点说明
- 长度判断遗漏:只有两字符串长度差值等于 1时,才需要调用
checkInsert;长度差大于 1 一定不相似; - 交换字符串顺序:若不统一长短串,需要额外写两套删除逻辑,
swap可简化代码; - 字符统计边界:
checkModify中允许0个不同字符(两串完全一致)、1个不同字符,超过 1 个直接判定不相似; - 模拟删除逻辑:删除字符是跳过指定下标,而非直接截断字符串,保证字符顺序不变。
