A33312. 相似字符串问题描述对于两个字符串A和B，如果A可以通过删除一个字符，或插入一个字符，或修改一个字符变成B，那么我们说A和B是相似的。比如 apple 可以通过插入一个字符变成 applee ，可以通过删除一个字符变成 appe ，也可以通过修改一个字符变成 bpple ，因此 apple 和 applee 、 appe 、 bpple 都是相似的。但 applee 并不能通过任意一个操作变成bp…
填空题
较难
知识点
题目描述
相似字符串
问题描述
对于两个字符串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， 的长度不超过50。保证A和B只包含小写字母。
输出描述
输出T行，对于每组A,B，如果它们相似，则输出 similar ，否则输出 not similar 。
特别提醒
在常规程序中，输入、输出时提供提示是好习惯。但在本场考试中，由于系统限定，请不要在输入、输出中附带任何提示信息。
样例输入 1
5
apple applee
apple appe
apple bpple
applee bpple
apple apple
样例输出 1
similar
similar
similar
not similar
similar
参考答案
def is_similar(A, B):
m, n = len(A), len(B)
if abs(m - n) > 1:
return False
if m == n:
diff = sum(1 for i in range(m) if A[i] != B[i])
return diff <= 1
else:
shorter = A if m < n else B
longer = B if m < n else A
i, j = 0, 0
diff = 0
while i < len(shorter) and j < len(longer):
if shorter[i] != longer[j]:
diff += 1
if diff > 1:
return False
j += 1
else:
i += 1
j += 1
return True
T = int(input())
for _ in range(T):
A, B = input().split()
if is_similar(A, B):
print("similar")
else:
print("not similar")
上一题
下一题