0072 编辑距离

中等 动态规划

算法思路

显然，读题可知，使用动态规划。编辑距离作为经典动态规划问题，其状态转移方程也不难总结：

\[ \displaystyle edit[i][j] = \min \left \{ \begin{array}{cc} edit[l-1][r] + 1 \\ edit[l][r-1] + 1 & \text{if word1[i] != word2[j] else} & edit[l-1][r-1] \\ edit[l-1][r-1] + 1 \end{array} \right. \]

显然，此算法时间复杂度为 \(O(mn)\)，空间复杂度为 \(O(mn)\)。

代码实现

edit-distance.c

int min(int a, int b, int c) {
    if (a < b && a < c) {
        return a;
    }
    if (b < a && b < c) {
        return b;
    }
    return c;
}

int minDistance(char* word1, char* word2) {
    int ret[502][502], index;
    int size1, size2;
    memset(ret, 0, 502 * 502 * sizeof(int));
    for (index = 0; word1[index]; index++) {
        ret[index + 1][0] = index + 1;
    }
    size1 = index;
    for (index = 0; word2[index]; index++) {
        ret[0][index + 1] = index + 1;
    }
    size2 = index;
    if (!size1 || !size2) {
        return ret[size1][size2];
    }
    for (int i = 1; word1[i - 1]; i++) {
        for (int j = 1; word2[j - 1]; j++) {
            if (word1[i - 1] == word2[j - 1]) {
                ret[i][j] = ret[i - 1][j - 1];
            } else {
                ret[i][j] = min(ret[i - 1][j] + 1, ret[i][j - 1] + 1,
                                ret[i - 1][j - 1] + 1);
            }
        }
    }
    return ret[size1][size2];
}