Edit Distance

Problem

Compute the Levenshtein edit distance between strings a and b: the minimum number of single-character insertions, deletions or substitutions needed to turn a into b.

Use dynamic programming over prefixes where a match copies the diagonal and a mismatch takes 1 plus the minimum of the diagonal, upper and left neighbours. Two empty strings have distance 0.

Hint

The first row and column encode the cost of building each prefix from an empty string.

Test cases

case 1

in: ["kitten","sitting"]

expected: 3

case 2

in: ["",""]

expected: 0

case 3

in: ["abc",""]

expected: 3

case 4

in: ["flaw","lawn"]

expected: 2

case 5

in: ["intention","execution"]

expected: 5

Starter codePython

def edit_distance(a, b):
    # Your code here
    pass

5 test cases · run your code against them in the editor