Minimum Editing Distance

Minimum editing distance is to compute the minimum number of operations that transform a string X to another string Y by inserting, deleting and changing characters. This problem is solved by dynamic programming.

int m, n, dp[2][N];
char str1[N], str2[N];

int min_edit_dist(){
    int i, j, pre, cur, u, v;

    pre = 0, cur = 1;
    m = strlen(str1+1);
    n = strlen(str2+1);

    for (i = 0; i <= n; i++) dp[0][i] = i;
    for (i = 1; i <= m; i++){
        dp[cur][0] = i;
        for (j = 1; j <= n; j++){
            u = dp[pre][j]+1;
            v = dp[cur][j-1]+1;
            if (str1[i] == str2[j])
               dp[cur][j] = MIN(dp[pre][j-1], MIN(u, v));
            else
               dp[cur][j] = MIN(dp[pre][j-1] + 2, MIN(u, v));
        }
        pre ^= 1; cur ^= 1;
    }
    return dp[pre][n];
}