Edit distance with operations

The edit distance between two strings is the smallest number of single-character edits, insertions, deletions and replacements, that turn one into the other; it is also called the Levenshtein distance. “Mysore” is 2 edits from “Mysuru” and “Hydrabad” 1 from “Hyderabad”, which is how a search box still finds the city someone meant. Interviews ask for the number first and then for the edits themselves. Both come from one table of (n + 1)(m + 1) cells, filled in O(nm) time for strings of n and m characters.

The problem: typed names against an official list

Problem A: the edit distance. Given strings a and b, return the fewest insertions, deletions and replacements of single characters that turn a into b; each edit costs 1. Limits: 0 ≤ n, m ≤ 1,000.

• "mysore" to "mysuru": 2, two replacements.
• "vishakapatnam" to "visakhapatnam": 2, one deletion and one insertion.
• "" to "agra": 4 insertions.

Problem B: the operations. Also return one cheapest list of edits, first to last, each with its position in the typed name.

The brute force, and why it fails at these sizes

Look at the first character of each string. Try keeping or replacing it, deleting it from a and inserting the character of b, solve what is left the same way, and take the cheapest of the three. Every call makes three more, so the number of calls explodes: 13,483 for two names of 6 letters, 897,625 for names of 8 and 9 letters, about 2.1 billion for two of 13 letters and 1.45 × 10²² for two of 30. The answers are right; the time is hopeless long before the limit of 1,000 characters.

# Edit distance by brute force: at every pair of positions, try deleting, inserting and replacing (or keeping an
# equal letter), and take the cheapest. Every call is counted, so the growth shows on short names.
calls = 0


def distance(a, b, i=0, j=0):
    """The fewest edits turning a[i:] into b[j:], trying every operation at every step."""
    global calls
    calls += 1
    if i == len(a) or j == len(b):
        return (len(a) - i) + (len(b) - j)  # only insertions or only deletions are left
    keep_or_replace = distance(a, b, i + 1, j + 1) + (a[i] != b[j])
    delete = distance(a, b, i + 1, j) + 1
    insert = distance(a, b, i, j + 1) + 1
    return min(keep_or_replace, delete, insert)


def calls_needed(n, m):
    """How many calls the brute force makes on strings of n and m letters (the same for any letters)."""
    c = [[1] * (m + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            c[i][j] = 1 + c[i - 1][j - 1] + c[i - 1][j] + c[i][j - 1]
    return c[n][m]


for typed, city in [("Pune", "Poona"), ("Mysore", "Mysuru"), ("Kolkatta", "Kolkata"), ("Hydrabad", "Hyderabad")]:
    calls = 0
    d = distance(typed.lower(), city.lower())
    print(f"{typed} -> {city}: distance {d}, {calls:,} calls")
print(f"Vishakapatnam -> Visakhapatnam (13 letters each) would make {calls_needed(13, 13):,} calls")
print(f"two strings of 30 letters: {calls_needed(30, 30):.2e} calls")

Pune -> Poona: distance 3, 1,021 calls
Mysore -> Mysuru: distance 2, 13,483 calls
Kolkatta -> Kolkata: distance 1, 162,817 calls
Hydrabad -> Hyderabad: distance 1, 897,625 calls
Vishakapatnam -> Visakhapatnam (13 letters each) would make 2,114,900,428 calls
two strings of 30 letters: 1.45e+22 calls

What to notice

• Two numbers describe every call: how many characters of a and of b are already used. That is at most (n + 1)(m + 1) different calls, about a million for two strings of 1,000, while the brute force makes billions on names of 13 letters.
• Each edit moves those numbers by one. A deletion uses a character of a, an insertion one of b, and a replacement or a kept character one of each.

Wagner and Fischer’s table stores the answer for every pair of prefixes. A walk back through the table lists the edits. The same table takes other costs: weighted edits, insertions and deletions only, or a swap of two neighbouring letters as one edit. When only small distances matter, a band of diagonals around the main one is enough.

The Wagner–Fischer table Pro: opens with a Pro, Premium or Ultimate pass