[数据结构与算法]583. 两个字符串的删除操作

问题等于len(s1)+len(s2) - len(最长子串)*2

直接求最长公共子序列

class Solution {
public:
    int minDistance(string word1, string word2) {
        const size_t n = word1.size();
        const size_t m = word2.size();
        int visit[505][5005] = {0};
        for (int i = 1; i <= n; i++)
            visit[1][i] = max(visit[1][i - 1], word1[i - 1] == word2[0] ? 1 : 0);
        for (int i = 2; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                visit[i][j] = max(visit[i - 1][j], max(visit[i][j - 1], visit[i - 1][j - 1] + (word2[i - 1] == word1[j - 1] ? 1 : 0)));
            }
        }
        return n + m - 2 * visit[m][n];
    }
};