Edit Distance

Find the minimum number of operations to turn string a into string b, where one operation inserts, deletes or replaces one character. (This is the Levenshtein distance, used in spell checkers.)

Input:

• line 1: a
• line 2: b

Output: the minimum number of operations.

Constraints: 1 ≤ length of a, b ≤ 500; lowercase letters.

Think about it: dp[i][j] = distance between the first i characters of a and the first j of b. Equal last characters cost nothing (dp[i−1][j−1]); otherwise 1 + min(insert, delete, replace). Fill the first row and column with 0, 1, 2, ….