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];
    }
};