编辑距离(一)

#define min(a,b) (a<b?a:b)
#define min3(a,b,c) (a<min(b,c)?a:min(b,c))
int editDistance(char* str1, char* str2 ) {
    int dp[1001][1001], i, j;
    for(i=1; i<=strlen(str1); i++) 
        dp[i][0] = i;
    for(i=1; i<=strlen(str2); i++) 
        dp[0][i] = i;
    for(i=1; i<=strlen(str1); i++) {
        for(j=1; j<=strlen(str2); j++) {
            if(str1[i-1]==str2[j-1]) 
                dp[i][j] = dp[i-1][j-1];
            else 
                dp[i][j] = min3(dp[i-1][j-1], dp[i-1][j], dp[i][j-1])+1;
        }
    }
    return dp[i-1][j-1];
}

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param str1 string字符串
 * @param str2 string字符串
 * @return int整型
 */
int editDistance(char* s, char* t ) {
    // write code here
    int m = strlen(s);
    int n = strlen(t);
    // if (m >= n + 2)
    //     return false;
    int** mined = (int**)malloc(sizeof(int*) * (m + 1));
    for (int i = 0; i <= m; i++) {
        mined[i] = (int*)calloc(n + 1, sizeof(int));
    }
    for (int ii = 1; ii <= m; ii++) {
        mined[ii][0] = ii;
    }
    for (int iii = 1; iii <= n; iii++) {
        mined[0][iii] = iii;
    }
    for (int j = 1; j <= m; j++) {
        for (int k = 1; k <= n; k++) {
            if (s[j - 1] == t[k - 1]) {
                mined[j][k] = mined[j - 1][k - 1];
            } 
            else {
                if ((mined[j - 1][k - 1] + 1) < (mined[j][k - 1] + 1)) {
                    if ((mined[j - 1][k - 1] + 1) < (mined[j - 1][k] + 1)) {
                        mined[j][k] = (mined[j - 1][k - 1] + 1);
                    } 
                    else {
                        mined[j][k] = (mined[j - 1][k] + 1);
                    }
                } 
                else {
                    if ((mined[j][k - 1] + 1) < (mined[j - 1][k] + 1)) {
                        mined[j][k] = (mined[j ][k - 1] + 1);
                    } 
                    else {
                        mined[j][k] = (mined[j - 1][k] + 1);
                    }

                }
                //mined[j][k]=((mined[j-1][k-1]+1)>(mined[j][k-1]+1):)
            }
        }
    }
    // if (mined[m][n] == 1)
    //     return true;
    return mined[m][n];
}