题解 | #牛群编号变更# 最长公共子序列 LCS

知识点

最长公共子序列 LCS

思路

两个序列的公共子序列部分是不需要更改的，剩下的则需要增加或者减少，所以只需要求出最长公共子序列，每个序列除去最长公共子序列的部分就是需要更改的部分。

定义 f[i][j]表示word1前i个字母和word2的前j个字母的最长公共子序列。

时间复杂度 $O(n^2)$

AC Code (C++)

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param word1 string字符串 
     * @param word2 string字符串 
     * @return int整型
     */
    int minDistance(string word1, string word2) {
        // 求lcs
        int n = word1.size(), m = word2.size();
        int f[n + 1][m + 1];
        memset(f, 0, sizeof f);
        f[0][0] = 0;
        int res = 0;
        for (int i = 1; i <= n; i ++) {
            for (int j = 1; j <= m; j ++) {
                f[i][j] = max(f[i - 1][j], f[i][j - 1]);
                if (word1[i - 1] == word2[j - 1]) f[i][j] = max(f[i][j], f[i - 1][j - 1] + 1);
            }
        }
        return n + m - 2 * f[n][m];
    }
};