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
andword2
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);
}
};
0 Comments
If you have any doubts/suggestion/any query or want to improve this article, you can comment down below and let me know. Will reply to you soon.