Edit (Levenshtein) Distance
Hard · Algorithms
The edit distance between two strings is the fewest single-character edits that turn one into the other. An edit is an insert, a delete, or a replace. Spell checkers use it to suggest close words.
Let dp[i][j] be the distance between a[:i] and b[:j]. Turning a string into the empty string takes one delete per character, so dp[i][0] = i and dp[0][j] = j. If a[i-1] == b[j-1] the last characters match and dp[i][j] = dp[i-1][j-1]. Otherwise take 1 + min(...) of delete (dp[i-1][j]), insert (dp[i][j-1]) and replace (dp[i-1][j-1]).
Write edit_distance(a, b) that returns the edit distance.