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

题目描述

给定两个单词 word1 和 word2 ，返回使得 word1 和 word2 相同所需的最小步数。

每步 可以删除任意一个字符串中的一个字符。

• 示例1：

输入：word2 = "sea", word2 = "eat"
输出： 2
解释：第一步将"sea"变为"ea", 第二步将"eat"变为"ea"

• 示例2：

输入：word2 = "leetcode", word2 = "etco"
输出： 4

提示：

• 1<=word1.length,wordl2.length<=500
• word1和word2只包含小写英文字母

解题思路

1. 确定dp数组的含义 dp[i][j]: 以i-1结尾的world1, 和以j-1结尾的world2, 想要达到相等，所需要删除的最少元素个数
2. 递推公式

• word1[i-1]与word2[j-1]相等时

  • dp[i][j] = dp[i-1][j-1]

• word1[i-1]与word2[j-1]不相等时

  • 删除word1[i-1], 最少操作次数为dp[i-1][j]+1
  • 删除word2[j-1], 最少操作次数为dp[i][j-1]+1
  • 删除word1[i-1]、word2[j-1], 最少操作次数为dp[i-1][j-1]+2(这种情况其实包含在上述两种情况中) dp[i][j] = min(dp[i-1][j]+1, dp[i][j-1]+1)

3. dp数组初始化 dp[i][0]: word2为空字符串，以i-1结尾的字符串word1需要删除i个元素才能和word2相同, dp[i][0]=i dp[0][j]: 同理, dp[0][j]=j
4. 确定遍历顺序 从上到下，从左到右
5. 打印dp数组

代码实现

核心模式

class Solution{
    public:
    int minDistance(string word1, string word2){
        vector<vector<int>> dp(word1.size() + 1, vector<int>(word2.size() + 1));
        // initialize the DP array
        for (int i = 0; i <= word1.size(); i++){
            dp[i][0] = i;
        }
        for (int j = 0; j <= word2.size(); j++){
            dp[0][j] = j;
        }

        // traversal
        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] = std::min(dp[i - 1][j] + 1, dp[i][j - 1] + 1);
                }
            }
        }
        
        return dp[word1.size()][word2.size()];
    }
};

ACM模式

"dynamicPro.h"

#include <iostream>
#include "dynamicPro.h"

class Solution{
    public:
    int minDistance(string word1, string word2){
        vector<vector<int>> dp(word1.size() + 1, vector<int>(word2.size() + 1));
        // initialize the DP array
        for (int i = 0; i <= word1.size(); i++){
            dp[i][0] = i;
        }
        for (int j = 0; j <= word2.size(); j++){
            dp[0][j] = j;
        }

        // traversal
        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] = std::min(dp[i - 1][j] + 1, dp[i][j - 1] + 1);
                }
            }
        }
        
        print2DVector(dp);
        return dp[word1.size()][word2.size()];
    }
};

int main(){
    Solution solution;
    cout << "Result1's DP array = " << solution.minDistance("sea", "eat") << endl;
    cout << "Result2's DP array = " << solution.minDistance("leetcode", "etco") << endl;

    return 0;
}

• 输出

Result1's DP array = [[0, 1, 2, 3], [1, 2, 3, 4], [2, 1, 2, 3], [3, 2, 1, 2]]
2
Result2's DP array = [[0, 1, 2, 3, 4], [1, 2, 3, 4, 5], [2, 1, 2, 3, 4], [3, 2, 3, 4, 5], [4, 3, 2, 3, 4], [5, 4, 3, 2, 3], [6, 5, 4, 3, 2], [7, 6, 5, 4, 3], [8, 7, 6, 5, 4]]
4