> For the complete documentation index, see [llms.txt](https://code-snippets.hbamithkumara.com/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://code-snippets.hbamithkumara.com/leetcode/problems/501-600/delete-operation-for-two-strings.md).

# 583. Delete Operation for Two Strings

### Description

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.

### Constraints

* `1 <= word1.length, word2.length <= 500`
* `word1` and `word2` consist of only lowercase English letters.

### Approach

### Links

* GeeksforGeeks
* [Leetcode](https://leetcode.com/problems/delete-operation-for-two-strings/)
* ProgramCreek
* YouTube

### **Examples**

{% tabs %}
{% tab title="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".
{% endtab %}

{% tab title="Example 2" %}
**Input:** word1 = "leetcode", word2 = "etco"

**Output:** 4
{% endtab %}
{% endtabs %}

### **Solutions**

{% tabs %}
{% tab title="Solution 1" %}

```java
/**
 * Time complexity : O(M*N), Where M is the size of the word1 and 
 *    N is the size of the word2.
 * Space complexity : O(M*N)
 */

class Solution {
    public int minDistance(String word1, String word2) {
        if(word1 == null && word2 == null) {
            return 0;
        } else if(word1 == null) {
            return word2.length();
        } else if(word2 == null) {
            return word1.length();
        }
        
        int l1 = word1.length(), l2 = word2.length();
        int[][] dp = new int[l1+1][l2+1];
        
        for(int i = 0; i <= l1; i++) {
            for(int j = 0; j <= l2; j++) {
                if(i == 0 || j == 0) {
                    dp[i][j] = i + j;
                } else if(word1.charAt(i-1) == word2.charAt(j-1)) {
                    dp[i][j] = dp[i-1][j-1];
                } else {
                    dp[i][j] = 1 + Math.min(dp[i][j-1], dp[i-1][j]);
                }
            }
        }
        
        return dp[l1][l2];
    }
}
```

{% endtab %}

{% tab title="Solution 2" %}

```java
/**
 * Time complexity : O(m*n), Where m is the size of the word1 and 
 *    n is the size of the word2.
 * Space complexity : O(n). dpdp array of size n is used.
 */

public class Solution {
    public int minDistance(String s1, String s2) {
        int[] dp = new int[s2.length() + 1];
        for (int i = 0; i <= s1.length(); i++) {
            int[] temp=new int[s2.length()+1];
            for (int j = 0; j <= s2.length(); j++) {
                if (i == 0 || j == 0)
                    temp[j] = i + j;
                else if (s1.charAt(i - 1) == s2.charAt(j - 1))
                    temp[j] = dp[j - 1];
                else
                    temp[j] = 1 + Math.min(dp[j], temp[j - 1]);
            }
            dp=temp;
        }
        return dp[s2.length()];
    }
}
```

{% endtab %}
{% endtabs %}

### **Follow up**

*