JLUVicent

72编辑距离&583两个字符串的删除操作

 
  • 2023年 04月11日
  • 0 阅读

day56

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

题目链接：583. 两个字符串的删除操作

解题思路：参考 视频

第一种思路：和求最长公共子序列代码相同，最终返回值不同，代码如下：

class Solution {
public:
    int minDistance(string word1, string word2) {
        // 1.参考最长公共子序列思路
        vector<vector<int>> dp(word1.size()+1,vector<int>(word2.size()+1,0));
        for( int i = 1; i <= word1.size(); i++){
            for( int j = 1; j <= word2.size(); j++){
                if( word1[i-1] == word2[j-1]){
                    dp[i][j] = dp[i-1][j-1]+1;
                }else{
                    dp[i][j] = max(dp[i-1][j],dp[i][j-1]);
                }
            }
        }
        return (word1.size()+word2.size()-2*dp[word1.size()][word2.size()]);	
    }
};

常规思路

1.确定dp数组及下标含义

以下标为i-1结尾的word1和以下标为j-1为结尾的word2相同所需要删除的次数为$dp[i][j]$.

2.确定递推公式

  • 当word1[i-1] == word2[j-1]，不需要删除，因此dp[i][j] = dp[i-1][j-1]
  • 当word1[i-1] != word2[j-1]，需要删除，删除word1[i-1]、删除word2[j-1]、和两个都删除，三者取最小值，即dp[i][j] =min(dp[i-1][j],dp[i][j-1],dp[i-1][j-1]+2) ，其实最后一种情况包含在前面的，可以去掉

3.初始化dp数组

$dp[i][0] = i$:对于空的word2数组，需要删除word1 i次才能使其相等

$dp[0][j]=j$:对于空的word1数组，需要删除word2 i次才能使其相等

4.确定遍历顺序

从前向后，从左向右

5.打印dp数组

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

class Solution {
public:
    int minDistance(string word1, string word2) {
        // // 1.参考最长公共子序列思路
        // vector<vector<int>> dp(word1.size()+1,vector<int>(word2.size()+1,0));
        // for( int i = 1; i <= word1.size(); i++){
        //     for( int j = 1; j <= word2.size(); j++){
        //         if( word1[i-1] == word2[j-1]){
        //             dp[i][j] = dp[i-1][j-1]+1;
        //         }else{
        //             dp[i][j] = max(dp[i-1][j],dp[i][j-1]);
        //         }
        //     }
        // }
        // return (word1.size()+word2.size()-2*dp[word1.size()][word2.size()]);
        // 2.本题常规思路
        vector<vector<int>> dp(word1.size()+1,vector<int>(word2.size()+1,0));
        for( int i = 0; i <= word1.size(); i++){
            dp[i][0] = i;
        }
        for( int j = 0; j <= word2.size(); j++){
            dp[0][j] = j;
        }
        for( int i = 1; i <= word1.size(); i++){
            for( int j = 1; j <= word2.size(); j++){
                if( word1[i-1] == word2[j-1]){
                    dp[i][j] = dp[i-1][j-1];
                }else{
                    dp[i][j] = min(dp[i-1][j]+1,dp[i][j-1]+1);
                }
            }
        }
        return dp[word1.size()][word2.size()];

    }
};

72.编辑距离

题目链接：72. 编辑距离

解题思路：参考 视频

1.确定dp数组及下标含义

将下标为i-1的单词word1转换为以下标j-1结尾的单词word2的最少操作数为$dp[i][j]$

2.递推公式

  • word1[i-1] == word2[j-1]时，不进行操作，$dp[i][j] = dp[i-1][j-1]+1$
  • word1[i-1] != word2[j-1]时，进行插入($dp[i][j-1]+1$，相当于对word2进行删除，逆向操作)，删除($dp[i-1][j]+1$，对word1进行删除）替换($dp[i-1][j-1]+1$，修改了word1相当于在之前的基础上➕1)，三者取最小值

3.初始化

$dp[i][0] = i;$ 相当于word2为空，删除i次

$dp[0][j]=j;$相当于word1为空，插入i次

4.遍历顺序

从左到右，从上到下

5.打印dp数组

class Solution {
public:
    int minDistance(string word1, string word2) {
        vector<vector<int>> dp(word1.size()+1,vector<int>(word2.size()+1,0));
        for( int i = 0; i <= word1.size(); i++){
            dp[i][0] = i;
        }
        for( int j = 0; j <= word2.size(); j++){
            dp[0][j] = j;
        }
        for( int i = 1; i <= word1.size(); i++){
            for( int j = 1; j <= word2.size(); j++){
                if( word1[i-1] == word2[j-1]){
                    dp[i][j] = dp[i-1][j-1];
                }else{
                    dp[i][j] = min(dp[i-1][j]+1,dp[i][j-1]+1);
                    dp[i][j] = min(dp[i][j],dp[i-1][j-1]+1);
                }
            }
        }
        return dp[word1.size()][word2.size()];
    }
};
搜索