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

Approach 1: Recursive

What are the subproblems in this case?

The idea is to process all characters one by one starting from either from the left or right sides of both strings. Let us traverse from the left corner, there are two possibilities for every pair of characters being traversed.

m: Length of str1 (first string)

n: Length of str2 (second string)

If the first characters of two strings are the same, nothing much to do. Ignore the first characters and get a count for the remaining strings. So we recur for lengths m-1 and n-1. Else (If first characters are not the same), we delete the first character of str1 or first character of str2, recursively compute the minimum cost for all two operations and take a minimum of two values.

Remove: Recur for m-1 and n

Remove: Recur for m and n-1

Solution (Recursive) TLE 1:

class Solution {
public:
    int minDistance(string word1, string word2) {
        if(word1.size()==0 || word2.size()==0)
        return max(word1.size(),word2.size());
        if(word1[0]==word2[0]) return minDistance(word1.substr(1),word2.substr(1));
        int op1=minDistance(word1.substr(1),word2);
        int op2=minDistance(word1,word2.substr(1));
        return min(op1,op2)+1;
    }
};

Time Complexity:- (2 power m)

Approach 2: Top Down

We can use memoization for the above solution and get rid of the TLE i.e. Top-Down DP

Solution 2: (Top Down):

class Solution {
public:
    int minDistance_memoization(string word1, string word2, int** dp) {
        if(word1.size()==0 || word2.size()==0)
        return max(word1.size(),word2.size());
        int n=word2.size();
        int m=word1.size();
        if(dp[m][n]!=-1) return dp[m][n];
        int ans;
        if(word1[0]==word2[0]) ans=minDistance_memoization(word1.substr(1),word2.substr(1),dp);
        else{
            int op1=minDistance_memoization(word1.substr(1),word2, dp);
            int op2=minDistance_memoization(word1,word2.substr(1),dp);
        ans=min(op1,op2)+1;
        }
        dp[m][n]=ans;
        return ans;
    }
    int minDistance(string word1, string word2)
    {
        int n=word2.size();
        int m=word1.size();
        int ** dp=new int* [m+1];
        for(int i=0;i<=m;i++)
        {
            dp[i]=new int [n+1];
            for(int j=0;j<=n;j++) dp[i][j]=-1;
        }
        return minDistance_memoization(word1,word2,dp);

    }
};

Approach 3: Dynamic Programming

If we draw the recursion tree, we can find that the same problem is being solved again and again We can see that many subproblems are solved, again and again, for example, eD(2, 2) is called three times. Since the same subproblems are called again, this problem has Overlapping Subproblems property. So this problem has both properties of a dynamic programming problem. Like other typical Dynamic Programming(DP) problems, recomputations of the same subproblems can be avoided by constructing a temporary array that stores the results of subproblems.

Solution 3: (Dynamic Programming):

class Solution {
public:
    int minDistance(string s, string t) {
            int m = s.size();
    int n = t.size();
    int **output = new int*[m+1];
    for(int i = 0; i <= m; i++) {
        output[i] = new int[n+1];
    }

    // Fill 1st row
    for(int j = 0; j <= n; j++) {
        output[0][j] = j;
    }

    // Fill 1st col
    for(int i = 1; i <= m; i++) {
        output[i][0] = i;
    }

    for(int i = 1; i <= m; i++) {
        for(int j = 1; j <= n; j++) {
            if(s[m-i] == t[n-j]) {
                output[i][j] = output[i-1][j-1];
            }
            else {
                int a = output[i-1][j];
                int b = output[i][j-1];
                output[i][j] = min(a,b) + 1;
            }
        }
    }

    return output[m][n];
    }
};

Time Complexity: O(m x n)

Auxiliary Space: O(m x n)