Dynamic Programming — Edit Distance

Return the minimum number of operations that turn a into b, where an
operation is inserting a character, deleting a character, or replacing one
character with another. This is the Levenshtein distance behind spell checkers
and git diff.

dist[i][j] is the distance between the first i characters of a and the
first j of b. If the last characters match, it is dist[i - 1][j - 1].
Otherwise it is 1 + the best of the three operations: delete
(dist[i - 1][j]), insert (dist[i][j - 1]) or replace
(dist[i - 1][j - 1]). The first row and column are the cost of building
from, or down to, an empty string. O(|a|·|b|).

Examples

solve('horse', 'ros')              → 3   // horse → rorse → rose → ros
solve('intention', 'execution')    → 5
solve('', 'abc')                   → 3

Constraints

• 0 <= a.length, b.length <= 500
• Case-sensitive.