Edit Distance

Given two strings, edit distance is the minimum number of edits needed to transform first string into second second. Edits includes insertion, deletion and substitutions of characters.

Subproblems:

Subproblem dp[i][j] represents the edit distance of first i characters of first string and first j characters of second string.

Function:

For every subproblems, we could encounter four situations: 1. Insert: dp[i][j] = 1 + dp[i][j - 1]; 2. Delete: dp[i][j] = 1 + dp[i - 1][j]; 3. Substitute: dp[i][j] = 1 + dp[i - 1][j - 1]; 4. Same character: dp[i][j] = dp[i - 1][j - 1];

Initialization:

for i=1:string1.length { dp[i][0] = i } for j=1:string2.length { dp[0][j] = j }