526互联

583. 两个字符串的删除操作

发布时间 2023-04-26 17:17:25作者: 穿过雾的阴霾
class Solution {
public:
    int f[510][510];//f[i][j]表示将s1前i个字符和s2前j个字符的最长公共子序列长度
    int minDistance(string word1, string word2) {
        int n=word1.size(),m=word2.size();
        word2=' '+word2;word1=' '+word1;
        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]==word2[j])  f[i][j]=max(f[i][j],f[i-1][j-1]+1);
            }
        return m+n-2*f[n][m];
    }
};