How many single-character edits turn one string into another? An edit is an insertion, a deletion or a substitution.

edit_distance("book", "back")  # 2
edit_distance("", "abc")       # 3

Let d[i][j] be the distance between the first i characters of a and the first j characters of b.

• d[i][0] = i: delete everything.
• d[0][j] = j: insert everything.
• If the last characters match, d[i][j] = d[i-1][j-1].
• Otherwise it is 1 plus the smallest of d[i-1][j] (delete), d[i][j-1] (insert) and d[i-1][j-1] (substitute).

Each row only depends on the row before it, so you can keep just two rows and save memory.

Write edit_distance(a, b) returning the minimum number of insertions, deletions and substitutions needed to turn a into b.

The explanation opens here once every check passes.