*This is part of a series of Leetcode solution explanations (index). If you liked this solution or found it useful,* *please like**this post and/or* *upvote**my solution post on Leetcode's forums.*

####
Leetcode Problem #583 (*Medium*): Delete Operation for Two Strings

####
*Description:*

*Description:*

(*Jump to*: *Solution Idea* || *Code*: *JavaScript* | *Python* | *Java* | *C++*)

Given two strings

`word1`

and`word2`

, returnthe minimum number of.stepsrequired to make`word1`

and`word2`

the sameIn one

step, you can delete exactly one character in either string.

####
*Examples:*

*Examples:*

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:*

*Constraints:*

`1 <= word1.length, word2.length <= 500`

`word1`

and`word2`

consist of only lowercase English letters.

####
*Idea:*

*Idea:*

(*Jump to*: *Problem Description* || *Code*: *JavaScript* | *Python* | *Java* | *C++*)

This problem is basically asking us to identify the **longest common subsequence** (**LCS**) between the two words (**W1, W2**). The answer will then be the combined difference between the length of the words and the length of the LCS.

For a typical LCS solution, we would use a **bottom-up** **dynamic programming** (**DP**) approach and use nested loops to compare each letter of each word against each other (**W1[i], W2[j]**). This would normally call for a DP array of size **(m + 1) * (n + 1)**, where **m = W1.length** and **n = W2.length**. Since the LCS process references the previous row and column for the target cell, we'll need the extra buffer of **0**-filled cells. Each cell in the DP array at **dp[i][j]** will represent the longest subsequence found between **W1.substr(0,i)** and **W2.susbtr(0,j)**. Our final answer will then be **dp[m][n]**.

Since the DP array is being built iteratively, in order, we can reduce the normal **space complexity** from **O(N * M)** by only keeping the current and last rows (**dpCurr, dpLast**) as we iterate through. This will drop the space complexity to **O(N)**. Doing this, we can also ensure that the shorter word is used for **N** by swapping the two words if necessary.

**Time Complexity: O(N * M)**where**N**and**M**are the lengths of the two words**Space Complexity: O(N)**where**N**is the length of the smaller of the two words

####
*Implementation:*

*Implementation:*

Javascript and Java will find it easier to iterate repeatedly through an array rather than a string, so we can initially **split()** or **toCharArray()** the two words (**WA1, WA2**).

####
*Javascript Code:*

*Javascript Code:*

(*Jump to*: *Problem Description* || *Solution Idea*)

```
var minDistance = function(W1, W2) {
let m = W1.length, n = W2.length
if (m < n) [W1, W2, m, n] = [W2, W1, n, m]
let WA1 = W1.split(""), WA2 = W2.split(""),
dpLast = new Uint16Array(n + 1),
dpCurr = new Uint16Array(n + 1)
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++)
dpCurr[j+1] = WA1[i] === WA2[j]
? dpLast[j] + 1
: Math.max(dpCurr[j], dpLast[j+1]);
[dpLast, dpCurr] = [dpCurr, dpLast]
}
return m + n - 2 * dpLast[n]
};
```

####
*Python Code:*

*Python Code:*

(*Jump to*: *Problem Description* || *Solution Idea*)

```
class Solution:
def minDistance(self, W1: str, W2: str) -> int:
m, n = len(W1), len(W2)
if m < n: W1, W2, m, n = W2, W1, n, m
dpLast, dpCurr = [0] * (n + 1), [0] * (n + 1)
for c1 in W1:
for j in range(n):
dpCurr[j+1] = dpLast[j] + 1 if c1 == W2[j] else max(dpCurr[j], dpLast[j+1])
dpLast, dpCurr = dpCurr, dpLast
return m + n - 2 * dpLast[n]
```

####
*Java Code:*

*Java Code:*

(*Jump to*: *Problem Description* || *Solution Idea*)

```
class Solution {
public int minDistance(String W1, String W2) {
int m = W1.length(), n = W2.length();
if (m < n) {
String tempStr = W1;
W1 = W2;
W2 = tempStr;
int tempInt = n;
n = m;
m = tempInt;
}
char[] WA1 = W1.toCharArray(), WA2 = W2.toCharArray();
int[] dpLast = new int[n+1], dpCurr = new int[n+1];
for (char c1 : WA1) {
for (int j = 0; j < n; j++)
dpCurr[j+1] = c1 == WA2[j]
? dpLast[j] + 1
: Math.max(dpCurr[j], dpLast[j+1]);
int[] tempArr = dpLast;
dpLast = dpCurr;
dpCurr = tempArr;
}
return m + n - 2 * dpLast[n];
}
}
```

####
*C++ Code:*

*C++ Code:*

(*Jump to*: *Problem Description* || *Solution Idea*)

```
class Solution {
public:
int minDistance(string W1, string W2) {
int m = W1.size(), n = W2.size();
if (m < n) swap(W1, W2), swap(n, m);
vector<int> dpLast(n+1, 0), dpCurr(n+1, 0);
for (char c1 : W1) {
for (int j = 0; j < n; j++)
dpCurr[j+1] = c1 == W2[j]
? dpLast[j] + 1
: max(dpCurr[j], dpLast[j+1]);
swap(dpLast, dpCurr);
}
return m + n - 2 * dpLast[n];
}
};
```

## Top comments (2)

My Java Solution by using LCS concept

## Rohithv07 / LeetCodeTopInterviewQuestions

## Leetcode Top Interview questions discussed in Leetcode. https://leetcode.com/explore/interview/card/top-interview-questions

## LeetCodeTopInterviewQuestions

Leetcode Top Interview questions discussed in Leetcode. leetcode.com/explore/interview/car...

Also Question answered from CodeSignal.com : app.codesignal.com/