编辑距离 Edit Distance

简介请点击leetcode 这里

这道题是动态规划。
动态规划的核心思想是缓存。
解决动态规划的主要方法是，找出状态转移方程式：

// s1, s2是输入字符串。arr[i][k]表示字符串s1[1...i]到字符串s2[1...k]的编辑距离。
// 字符串的下标从1开始。1...i表示是双闭区间

// 状态转移方程式如下:
arr[i][k] = min(arr[i-1][k] + 1, arr[i][k-1] + 1, arr[i-1][k-1] + (s1[i] == s2[k] ? 1: 0));

// 其中arr[0][k] 的长度是k, arr[i][0]的长度是i.
// 那么s1到s2的距离即是：arr[lenOfs1][lenOfs2]

int text_distance(const std::string &s1, const std::string &s2) {
    if (s1.empty() || s2.empty()) {
        return std::max<int>(s1.size(), s2.size());
    }

    const int N = s1.size();
    const int M = s2.size();

    int arr[N + 1][M + 1];
    memset(arr, 0, sizeof(arr));

    for (int i = 0; i <= N; i++) {
        arr[i][0] = i;
    }
    for (int j = 0; j <= M; j++) {
        arr[0][j] = j;
    }


    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= M; j++) {
            char c1 = s1[i - 1];
            char c2 = s2[j - 1];
            // pay attention to operator precedence.
            // arr[i - 1][j - 1] + ((c1 != c2) ? 1 : 0) != arr[i - 1][j - 1] + (c1 != c2) ? 1 : 0

            arr[i][j] = min(min(arr[i - 1][j] + 1, arr[i][j - 1] + 1), arr[i - 1][j - 1] + ((c1 != c2) ? 1 : 0));
        }
    }
    return arr[N][M];
}

输入:

zoologicoarchaeologist zoogeologist

输出:

10