代码随想录Day57、58 | 392.判断子序列 | 115. 不同的子序列 | 583. 两个字符串的删除操作 | 72. 编辑距离

392. 判断子序列

class Solution {
public:
    bool isSubsequence(string s, string t) {
        int m = s.size();
        int n = t.size();
        vectorint>> f(m+1,vector<int>(n+1,0)); //f[i][j]:s前i-1个字符，t前j-1个字符中字符数相等的个数。
        for(int i=1;i<=m;i++){
            for(int j=1;j<=n;j++){
                if(s[i-1]==t[j-1])
                f[i][j]=f[i-1][j-1]+1; //匹配，则长度加1
                else f[i][j] = f[i][j-1];  //若不匹配，则删除最后一个字符
            }
        }
        return f[m][n]==m;
    }
};

115. 不同的子序列

class Solution {
public:
    int numDistinct(string s, string t) {
        int mod = 1e9 + 7;
        int m = s.size();
        int n = t.size();
        vectorint>> f(m+1,vector<int>(n+1,0));
        for (int i = 0; i < m; i++) f[i][0] = 1;
        for(int i=1;i<=m;i++){
            for(int j=1;j<=n;j++){
                if(s[i-1]==t[j-1]){
                    f[i][j]=(f[i-1][j-1]+f[i-1][j])%mod; 
                }
                else{
                    f[i][j]=f[i-1][j]%mod;//两个字符串最后一个字符不相等，故删去最后一个字符重新匹配
                }
            }
        }
        return f[m][n];
    }
};

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

class Solution {
public:
    int minDistance(string word1, string word2) {
        int m = word1.size();
        int n = word2.size();
        vectorint>> f(m+1,vector<int>(n+1,0));  //计算两个字符串的公共长度
        for(int i=1;i<=m;i++){
            for(int j=1;j<=n;j++){
                if(word1[i-1]==word2[j-1]){
                    f[i][j]=f[i-1][j-1]+1;
                }
                else f[i][j] = max(f[i-1][j],f[i][j-1]);
            }
        }
        return m+n-2*f[m][n];  //两个字符串各减去公共字符串的长度即为需要删除的步数
    }
};

72. 编辑距离

class Solution {
public:
    int minDistance(string word1, string word2) {
        int n=word1.size();
        int m=word2.size();
        vectorint>>f(n+1,vector<int>(m+1,0)); //f[i][j]:word1前i个字符转换为word2前j个字符需要的步数
        for(int i=0;i<=n;i++){  //赋初值
            f[i][0]=i;  
        }
        for(int j=0;j<=m;j++){
            f[0][j]=j;
        }
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                if(word1[i-1]==word2[j-1]){ //最后一位相等，不需要任何编辑
                    f[i][j]=f[i-1][j-1];
                }
                else {
                    f[i][j]=min(f[i-1][j]+1,min(f[i][j-1]+1,f[i-1][j-1]+1));
                    //最后一位不相等，方法一：删除word1最后一个字符
                    //方法二：删除word2最后一个字符，等价于word1增加一个字符
                    //方法三：替换最后一个字符，即f[i-1][j-1]+1。
                }
            }
        }
        return f[n][m];
    }
};