# 583. Delete Operation for Two Strings

Given 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.

``````class Solution {
public:
int minDistance(string word1, string word2) {
int n1 = word1.size(), n2 = word2.size();
vector<vector<int>> dp(n1 + 1, vector<int>(n2 + 1, 0));
for (int i = 1; i <= n1; ++i) {
for (int j = 1; j <= n2; ++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 n1 + n2 - 2 * dp[n1][n2];
}
};
``````

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

``````class Solution {
public:
int minDistance(string word1, string word2) {
int n1 = word1.size(), n2 = word2.size();
vector<vector<int>> memo(n1 + 1, vector<int>(n2 + 1, 0));
return helper(word1, word2, 0, 0, memo);
}
int helper(string word1, string word2, int p1, int p2, vector<vector<int>>& memo) {
if (memo[p1][p2] != 0) return memo[p1][p2];
int n1 = word1.size(), n2 = word2.size();
if (p1 == n1 || p2 == n2) return n1 - p1 + n2 - p2;
if (word1[p1] == word2[p2]) {
memo[p1][p2] = helper(word1, word2, p1 + 1, p2 + 1, memo);
} else {
memo[p1][p2] = 1 + min(helper(word1, word2, p1 + 1, p2, memo), helper(word1, word2, p1, p2 + 1, memo));
}
return memo[p1][p2];
}
};
``````

Github 同步地址：

https://github.com/grandyang/leetcode/issues/583

Edit Distance

Minimum ASCII Delete Sum for Two Strings

Longest Common Subsequence

https://leetcode.com/problems/delete-operation-for-two-strings/

https://leetcode.com/problems/delete-operation-for-two-strings/discuss/103273/dynamic-programming-and-memoization-solution

https://leetcode.com/problems/delete-operation-for-two-strings/discuss/103214/Java-DP-Solution-(Longest-Common-Subsequence)

https://leetcode.com/problems/delete-operation-for-two-strings/discuss/103258/two-pointers-recursive-java-solution-with-memoization

LeetCode All in One 题目讲解汇总(持续更新中…)

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation