edit_distance_Levenshtein_distance.txt

int min(int a, int b)
{
    return (a < b) ? a : b;
}

int mat[502][502];

/* Levenshtein distance */
int minDistance(char * word1, char * word2){
    int w1_len = strlen(word1);
    int w2_len = strlen(word2);
    
    // fill 0-th row
    for (int i = 0; i < w2_len + 1; i++) {
        mat[0][i] = i;
    }
    
    // fill 0-th col
    for (int i = 0; i < w1_len + 1; i++) {
        mat[i][0] = i;
    }
    
    for (int i = 1; i < w1_len + 1; i++) {
        for (int j = 1; j < w2_len + 1; j++) {
            if (word1[i - 1] == word2[j - 1]) {
                    mat[i][j] = mat[i - 1][j - 1];
            } else {
                int insertion = mat[i - 1][j];
                int deletion = mat[i][j - 1];
                int substitution = mat[i - 1][j - 1];
                
                int min1 = min(insertion, deletion);
                int min2 = min(min1, substitution);
                
                mat[i][j] = min2 + 1;
            }
        }
    }
    
    return mat[w1_len][w2_len];
}