LeetCode #583:Delete Operation For Two Strings(两个字符串的删除操作)

题目描述

状态定义:设 dp[i][j] 为字符串 word1[0…i-1],和字符串 word2[0…j-1],想要达到相等,所需要删除元素的最少次数。

与前面的题解不同的是,本题的状态并没有定义成 “dp[i][j] 为字符串 word1[0…i],和字符串 word2[0…j],想要达到相等,所需要删除元素的最少次数”,而是整体后移了一位。这么做的考虑是将下标 0 留出来表示空串,方便下面 dp 数组的初始化。否则,初始化第 0 行和第 0 列的过程会比较麻烦。

dp[i][j] 的转移有两种情况:

① 当 word1[i-1] == word2[j-1] 时,即两个串末尾相等时,不删除末尾的字符,将问题转化为删除 word1[0…i-2] 与 word2[0…j-2] 中的字符,其状态转移方程为:

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

② 当 word1[i-1] != word2[j-1] 时,我们可以尝试删除 word1 末尾的字符(word1[i-1])、删除 word2(word2[j-1])末尾的字符、同时删除 word1、word2 末尾的字符(word1[i-1] 与 word2[j-1])。这三种情况需要取最小值,状态转移方程为:

dp[i][j] = min(dp[i - 1][j] + 1, dp[i][j - 1] + 1, dp[i - 1][j - 1] + 2);

dp 数组初始化方面,由于下标 0 被预留作为空串,故第 0 列 dp[i][0] 应初始化为 i(word2 为空串,所以 word1[0…i-1] 需要删成空串才能和 word2 相等);同理第 0 行 dp[0][j] 应初始化为 j。

代码实现如下:

class Solution {
public:
    int minDistance(string word1, string word2) {
        int n = word1.length();
        int m = word2.length();
        vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));
        dp[0][0] = 0;
        for(int i = 1; i <= n; i ++)
            dp[i][0] = i;

        for(int j = 1; j <= m; j ++) 
            dp[0][j] = j;

        for(int i = 1; i <= n; i ++) {
            for(int j = 1; j <= m; 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] + 2, min(dp[i - 1][j] + 1, dp[i][j - 1] + 1));
            }
        }

        return dp[n][m];
    }
};

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注