Problem Statement

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

Problem Link

Delete Operation for Two Strings - LeetCode

Approach

Minimum no of deletions to make strings s1 and s2 same = (l1-lcs) + (l2-lcs)
                                                       = l1 + l2 - 2*lcs

where, l1 = length of string s1
       l2 = length of string s2
       lcs = lcs(s1,s2)

Code

class Solution {
public:
    int minDistance(string word1, string word2) {
        
        int l1 = word1.size(), l2 = word2.size();
        vector<vector<int>> dp(l1+1,vector<int>(l2+1));
        
        for(int i=0;i<=l1;i++)
        {
            for(int j=0;j<=l2;j++)
            {
                if(!i||!j)
                    dp[i][j] = 0;
                
                else if(word1[i-1]==word2[j-1])
                    dp[i][j] = 1 + dp[i-1][j-1];
                
                else
                    dp[i][j] = max(dp[i-1][j],dp[i][j-1]);
            }
        }
        int lcs = dp[l1][l2];
        //no. of char deleted = (l1-lcs) + (l2-lcs)
        return l1+l2-(2*lcs);
            
    }
};

Complexity Analysis

Time and Space Complexity of the above implementation is O(mn)