Levenshtein Edit Distance

Compute the Levenshtein edit distance between two strings.

The edit distance is the smallest number of single-character edits that turn one string into the other. An edit is an insertion, a deletion or a substitution, each with a cost of 1. Spell checkers, fuzzy search and the word error rate in speech recognition all use it.

Fill a table D of size (len(a) + 1, len(b) + 1), where D[i, j] is the distance between the first i characters of a and the first j of b:

D[i, 0] = i,   D[0, j] = j
D[i, j] = min(D[i - 1, j] + 1,                         # delete a[i-1]
              D[i, j - 1] + 1,                         # insert b[j-1]
              D[i - 1, j - 1] + (a[i-1] != b[j-1]))    # substitute or match

The answer is D[len(a), len(b)].

Function signature

def edit_distance(a, b):

Example

Input

edit_distance("flaw", "lawn")

Output

2

Reasoning

Delete the f to get law, then insert n at the end to get lawn. That is two edits. No single edit can do it, because the strings differ in their first and last characters.

Constraints and notes

• The strings can be empty. The distance from "" to b is len(b).
• The distance is symmetric.
• You only need two rows of the table at a time, which uses O(len(b)) memory.
• Return an int.