# 583. Delete Operation for Two Strings | Leetcode Solution

## 583. Delete Operation for Two Strings | Leetcode Solution

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.

class Solution {
public:
int dp[501][501];
int fun(string &a,string &b, int i,int j) {
if(i==a.size() && j==b.size())return 0;
if(i==a.size()||j==b.size())return max(a.size()-i,b.size()-j);
if(dp[i][j]!=-1)return dp[i][j];
if(a[i]==b[j])return dp[i][j]=fun(a,b,i+1,j+1);
return dp[i][j]=1+min(fun(a,b,i+1,j),fun(a,b,i,j+1));
}

int minDistance(string word1, string word2) {
memset(dp,-1,sizeof(dp));
return fun(word1,word2,0,0);
}
};