题解 | #编辑距离(一)#

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param str1 string字符串 
 * @param str2 string字符串 
 * @return int整型
 */

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

int editDistance(char* str1, char* str2 ) {
    // write code here
    int len1 = strlen(str1), len2 = strlen(str2);
    int dp[len2 + 1];
    for(int i = 0; i <= len2; i++) dp[i] = i;

    for(int j = 1; j <= len1; j++) {
        int leftup = dp[0];
        dp[0]++;
        for(int i = 1; i <= len2; i++) {
            int temp = dp[i];
            if(str1[j - 1] == str2[i - 1]) dp[i] = leftup;
            else {
                dp[i] = min(dp[i - 1],leftup,dp[i]) + 1;
            }
            leftup = temp;
        }
    }
    return dp[len2];
}