Check quickly whether two words differ by a single typo.
What to build
A program that says whether pairs of words are the same, one edit apart, or further apart.
Requirements
- One edit is inserting, deleting or substituting a single character.
- For each pair print
a b: same,a b: one editora b: no.
Input
Line 1: n. Then n lines, each with two words.
Output
n lines.
Constraints
n ≤ 1,000; words have at most 50 characters.
Example
Input:
3
cat cut
cat cart
cat dog
Output:
cat cut: one edit
cat cart: one edit
cat dog: no
Why it works
With equal lengths only a substitution is possible, so exactly one position must differ; with lengths differing by one, the shorter word must be the longer word with one character removed.
Examples
Example 1 · Input
3 cat cut cat cart cat dog
Expected output
cat cut: one edit cat cart: one edit cat dog: no
Example 2 · Input
2 same same form from
Expected output
same same: same form from: no
Prompts inside input() are ignored when checking, so input("n: ") is fine.
Hints
Hint 1
Words of equal length are one edit apart when exactly one position differs.
Hint 2
If the lengths differ by one, try deleting each character of the longer word: `b[:i] + b[i + 1:]`.
Solution
Show one correct solution (try it yourself first)
def one_edit(a, b):
if len(a) == len(b):
return sum(1 for x, y in zip(a, b) if x != y) == 1
if len(a) > len(b):
a, b = b, a
if len(b) - len(a) != 1:
return False
return any(b[:i] + b[i + 1:] == a for i in range(len(b)))
for _ in range(int(input())):
a, b = input().split()
print(f"{a} {b}: {'same' if a == b else 'one edit' if one_edit(a, b) else 'no'}")