Edit Distance.

Problem Statement: The edit distance between two words is the minimum number of letter insertions, letter deletions and letter substitutions required to transform one word into another. For e.g. edit distance between "food"and "money" is 4. Below is the equation and the code for the problem,

min[i, j] = MIN(min[i-1, j] + 1, min[i, j-1] + 1, min[i-1, j-1] + (A[i] != B[j]))

#define MIN(a, b) ((a)<(b))?(a):(b)

int min[100][100];

int editDistance(char* A, char* B)
{
    int n = strlen(A);
    int m = strlen(B);

    int i, j;

    for(i=0; i <= n; i++)
        min[i][0] = i;
    
    for(j=0; j <= m; j++)
        min[0][j] = j;

    for(i=1; i <= n; i++)
    {
        for(j=1; j <= m; j++)
        {
            min[i][j] = MIN(min[i-1][j] + 1, min[i][j-1] + 1);
            min[i][j] = MIN(min[i][j], min[i-1][j-1] + (A[i-1]!=B[j-1]));
        }
    }

    return min[n][m];
}

int main()
{
    char A[50] = {0, };
    char B[50] = {0, };

    sprintf(A, "%s", "food");
    sprintf(B, "%s", "money");

    printf("EDIT DISTANCE: %d\n", editDistance(A, B));
    return 0;
}