Algorithm
Problem Name: 583. Delete Operation for Two Strings
Given two strings word1 and word2, return the minimum number of steps required to make word1 and word2 the same.
In one step, you can delete exactly one character in either string.
Example 1:
Input: word1 = "sea", word2 = "eat" Output: 2 Explanation: You need one step to make "sea" to "ea" and another step to make "eat" to "ea".
Example 2:
Input: word1 = "leetcode", word2 = "etco" Output: 4
Constraints:
1 <= word1.length, word2.length <= 500word1andword2consist of only lowercase English letters.
Code Examples
#1 Code Example with C++ Programming
Code -
C++ Programming
class Solution {
public:
int minDistance(string word1, string word2) {
// dp[i][j] = word1[i - 1] == word2[j - 1] ? dp[i - 1][j - 1] + 1 : max(dp[i - 1][j], dp[i][j - 1]);
vector < vector<int>>dp(word1.size() + 1, vector<int>(word2.size() + 1));
for(int i = 0; i < = word1.size(); i++)
for(int j = 0; j < = word2.size(); j++)
dp[i][j] = (!i || !j) ? 0 : (word1[i - 1] == word2[j - 1]) ? dp[i - 1][j - 1] + 1 : max(dp[i - 1][j], dp[i][j - 1]);
int LCS = dp[word1.size()][word2.size()];
return (word1.size() - LCS) + (word2.size() - LCS);
}
};
Input
word1 = "sea", word2 = "eat"
Output
2
#2 Code Example with Java Programming
Code -
Java Programming
class Solution {
public int minDistance(String word1, String word2) {
int[][] dp = new int[word1.length() + 1][word2.length() + 1];
return word1.length() + word2.length() - 2 * longestCommonSubsequence(word1, word2, word1.length(), word2.length(), dp);
}
private int longestCommonSubsequence(String word1, String word2, int m, int n, int[][] dp) {
if (m == 0 || n == 0) {
return 0;
}
if (dp[m][n] > 0) {
return dp[m][n];
}
if (word1.charAt(m - 1) == word2.charAt(n - 1)) {
dp[m][n] = 1 + longestCommonSubsequence(word1, word2, m - 1, n - 1, dp);
} else {
dp[m][n] = Math.max(longestCommonSubsequence(word1, word2, m - 1, n, dp), longestCommonSubsequence(word1, word2, m, n - 1, dp));
}
return dp[m][n];
}
}
Input
word1 = "sea", word2 = "eat"
Output
2
#3 Code Example with Javascript Programming
Code -
Javascript Programming
const minDistance = function (word1, word2, memo = new Map()) {
if (word1 === word2) return 0
if (word1 === '' || word2 === '') return Math.max(word1.length, word2.length)
const len1 = word1.length
const len2 = word2.length
if (memo.has(`${word1}-${word2}`)) return memo.get(`${word1}-${word2}`)
let res
if (word1[len1 - 1] === word2[len2 - 1]) {
res = minDistance(word1.slice(0, len1 - 1), word2.slice(0, len2 - 1), memo)
} else {
res =
1 +
Math.min(
minDistance(word1.slice(0, len1 - 1), word2, memo),
minDistance(word1, word2.slice(0, len2 - 1), memo)
)
}
memo.set(`${word1}-${word2}`, res)
return res
}
Input
word1 = "leetcode", word2 = "etco"
Output
4
#4 Code Example with Python Programming
Code -
Python Programming
class Solution:
def minDistance(self, w1, w2):
m, n = len(w1), len(w2)
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(m + 1):
for j in range(n + 1):
if i == 0 or j == 0:
dp[i][j] = i + j
elif w1[i - 1] == w2[j - 1]:
dp[i][j] = dp[i - 1][j - 1]
else:
dp[i][j] = min(dp[i][j - 1] + 1, dp[i - 1][j] + 1)
return dp[-1][-1]
Input
word1 = "leetcode", word2 = "etco"
Output
4