Edit Distance Table Cache

Problem

Compute the Levenshtein edit distance with a dynamic programming table.

Insertions, deletions, and substitutions each cost 1. Fill the table row by row, reusing the previous row so only two rows are kept in memory.

Return the edit distance between a and b.

Hint

The three neighboring cells represent substitution, deletion, and insertion.

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

Starter codePython

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

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