Solution: Delete Operation for Two Strings
Tags: algorithms, javascript, java, python
Published: 2021-05-07 09:11:28

*This is part of a series of Leetcode solution explanations ([index](https://dev.to/seanpgallivan/leetcode-solutions-index-57fl)). If you liked this solution or found it useful,* ***please like*** *this post and/or* ***upvote*** *[my solution post on Leetcode's forums](https://leetcode.com/problems/delete-operation-for-two-strings/discuss/1195718).*

---

#### [Leetcode Problem #583 (*Medium*): Delete Operation for Two Strings](https://leetcode.com/problems/delete-operation-for-two-strings/)

---

#### ***Description:***

<br />(*Jump to*: [*Solution Idea*](#idea) || *Code*: [*JavaScript*](#javascript-code) | [*Python*](#python-code) | [*Java*](#java-code) | [*C++*](#c-code))

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

---

#### ***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:***
>
 - `1 <= word1.length, word2.length <= 500`
 - `word1` and `word2` consist of only lowercase English letters.

---

#### ***Idea:***

<br />(*Jump to*: [*Problem Description*](#description) || *Code*: [*JavaScript*](#javascript-code) | [*Python*](#python-code) | [*Java*](#java-code) | [*C++*](#c-code))

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

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:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```javascript
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:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```python
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:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```java
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:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```c++
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];
    }
};
```