当前位置：首页 > article >正文

代码随想录训练营第45天|编辑距离

article 2024/9/28 23:49:30

115. 不同的子序列

class Solution {
public:
    int numDistinct(string s, string t) {
        s.insert(s.begin(),' ');
        t.insert(t.begin(),' ');
        int ns=s.length();
        int nt=t.length();
        vector<vector<uint64_t>> dp(ns,vector<uint64_t>(nt,0));
        for(int i=0; i<ns; i++){
            dp[i][0]=1;
        }
        for(int i=1; i<ns; i++){
            for(int j=1; j<nt; j++){
                if(s[i]==t[j])
                    dp[i][j]=dp[i-1][j-1]+dp[i-1][j];
                else
                    dp[i][j]=dp[i-1][j];
            }
        }
        return dp[ns-1][nt-1];
    }
};

dp[i][j]:截止到s[i],t[j]（包含）的两个子串所形成的子序列个数。

转移方程：

1.若结尾不等，则s[i]无法发挥作用，只能由i-1前的子串构建，个数等同于dp[i-1][j]

2.若结尾相等，则有两种选择：

s[i]参与构建，则s的i-1前的子串要负责构建t的j-1部分的序列，个数为dp[i-1][j-1]
s[i]不参与构建，则s的i-1前的子串要负责构建全部t的序列，个数为dp[i-1][j]

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

class Solution {
public:
    int minDistance(string word1, string word2) {
        word1.insert(word1.begin(),' ');
        word2.insert(word2.begin(),' ');
        int n1=word1.length(), n2=word2.length();
        vector<vector<int>> dp(n1,vector<int>(n2,0));
        for(int j=1; j<n2; j++){
            dp[0][j]=j;
        }
        for(int i=1; i<n1; i++)
            dp[i][0]=i;
        for(int i=1; i<n1; i++){
            for(int j=1; j<n2; j++){
                if(word1[i]==word2[j])
                    dp[i][j]=dp[i-1][j-1];
                else
                    dp[i][j]=min(dp[i-1][j],dp[i][j-1])+1;
            }
        }
        return dp[n1-1][n2-1];

    }
};

dp[i][j]:由word1[0:i]到word2[0:j]的最小删除操作数目

转移方程：

1.若结尾相等，则不会增加操作数，由dp[i-1][j-1]转移而来

2.若结尾不等，则有两种可能：

删除word1的结尾，由dp[i-1][j]转移而来
删除word2的结尾，由dp[i][j-1]转移而来

取二者较小。

72. 编辑距离

class Solution {
public:
    int minDistance(string word1, string word2) {
        word1.insert(word1.begin(),' ');
        word2.insert(word2.begin(),' ');
        int n1=word1.length(), n2=word2.length();
        vector<vector<int>> dp(n1,vector<int>(n2,0));
        for(int j=1; j<n2; j++)
            dp[0][j]=j;
        for(int i=1; i<n1; i++)
            dp[i][0]=i;
        for(int i=1; i<n1; i++){
            for(int j=1; j<n2; j++){
                if(word1[i]==word2[j])
                    dp[i][j]=dp[i-1][j-1];
                else
                    dp[i][j]=min({dp[i-1][j],dp[i][j-1],dp[i-1][j-1]})+1;
            }
        }
        return dp[n1-1][n2-1];
    }
};

dp[i][j]:由word1[0:i]到word2[0:j]的编辑距离

转移方程：

1.若结尾相等，则不会增加编辑距离，由dp[i-1][j-1]转移而来

2.若结尾不等，则有三种可能：