【week10】583. Delete Operation for Two Strings 解题报告

583. Delete Operation for Two Strings

题目

iven two words word1 and word2, find the minimum number of steps required to make word1 and word2 the same, where in each step you can delete one character in either string.

Example 1:

Input: "sea", "eat"
Output: 2
Explanation: You need one step to make "sea" to "ea" and another step to make "eat" to "ea".

Note:

1. The length of given words won’t exceed 500.
2. Characters in given words can only be lower-case letters.

解题报告

题目很简单，给定两个字符串，可以删除其中任意 $n$ 个字符，求使得两个字符串相同的最小 $n$。

这题和编辑距离差不多，只是可以做的操作变了，可以定义子问题为：$dp[i][j]$ 等于使得 $word1(1,i)=word2(1,j)$ 相等的最小 $n$。

显然要使 $word1(1,i)=word2(1,j)$，可以有三种途径：

• 先让 $word1(1,i-1)=word2(1,j)$，再删除 $word1[i]$。
• 先让 $word1(1,i)=word2(1,j-1)$，再删除 $word[j]$。
• 先让 $word1(1,i-1)=word2(1,j-1)$，如果 $word1[i]\ne word2[j]$，就把 $word1[i]$ 和 $word2[j]$ 都删掉。

显然，$dp[i][j]$ 为上述三种途径中花费最小的那个。另外，当其中一个字符串为空串时要让另一个长度为 $k$ 的字符串与之相等需要的最小 $n$ 即 $k$（删除另一个字符串的所有字符）。

得到了状态转移方程后就很简单了。

Solution

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)
                dp[i][j] = min(min(dp[i - 1][j] + 1, dp[i][j - 1] + 1), dp[i - 1][j - 1] + (word1[i - 1] == word2[j - 1] ? 0 : 2));
        return dp.back().back();
    }
};