## 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 <= 500`
• `word1` and `word2` consist 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>dp(word1.size() + 1, vector(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);
}
};
``````
Copy The Code &

Input

cmd
word1 = "sea", word2 = "eat"

Output

cmd
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];
}
}
``````
Copy The Code &

Input

cmd
word1 = "sea", word2 = "eat"

Output

cmd
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
}
``````
Copy The Code &

Input

cmd
word1 = "leetcode", word2 = "etco"

Output

cmd
4

### #4 Code Example with Python Programming

```Code - Python Programming```

``````
class Solution:
def minDistance(self, w1, w2):
m, n = len(w1), len(w2)
dp = [ * (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]
``````
Copy The Code &

Input

cmd
word1 = "leetcode", word2 = "etco"

Output

cmd
4