NLP: One edit apart?

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 edit or a 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'}")

Lesson: Edit distance and spelling correction →