Delete Operation for Two Strings

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.

Approach - Tabulation 1D

• O(m*n), O(n)

class Solution {
    public int minDistance(String word1, String word2) {
        int m = word1.length(), n = word2.length();
        int[] dp = new int[n+1];
 
        // Base case for i = m: word1 is empty → delete all of word2[j..]
        for (int i = 0; i < n; i++)
            dp[i] = n - i;
 
        for (int i = m - 1; i >= 0; i--) {
            // prev holds dp[i+1][j+1] from the *previous* iteration of j
            int prev = dp[n]; // initially dp[i+1][n] = (n - n) = 0
            dp[n] = m - i; // dp[i][n] = delete all of word1[i..]
 
            for (int j = n - 1; j >= 0; j--) {
                int tmp = dp[j];
                // chars match → no extra deletion beyond the interior
                if (word1.charAt(i) == word2.charAt(j))
                    dp[j] = prev;
                // chars differ → delete one char (either from word1 or word2)
                else
                    dp[j] = 1 + Math.min(dp[j], dp[j+1]);
                    //   dp[j] = old dp[i+1][j]
                    // dp[j+1]= dp[i][j+1]
                prev = tmp; // shift prev → old dp[i+1][j]
            }
        }
        // dp[0] now holds dp[0][0] for the full strings
        return dp[0];
    }
}

Approach - Tabulation 2D

• We need to cover the case for the deleting rest element we did before
• O(m*n), O(m*n) O(m+n) is for recursion stack

class Solution {
    public int minDistance(String word1, String word2) {
        int m = word1.length(), n = word2.length();
        int[][] dp = new int[m+1][n+1];
 
        for (int j = 0; j < n; j++)
            dp[m][j] = n - j;
 
        for (int i = 0; i < m; i++)
            dp[i][n] = m - i;
 
        for (int i = m - 1; i >= 0; i--) {
            for (int j = n - 1; j >= 0; j--) {
                if (word1.charAt(i) == word2.charAt(j))
                    dp[i][j] = dp[i+1][j+1];
                else
                    dp[i][j] = 1 + Math.min(dp[i+1][j], dp[i][j+1]);
            }
        }
 
        return dp[0][0];
    }
}

Approach - Memoization

• We use 2D DP nothing unusual

class Solution {
    public int[][] dp;
    public int minDistance(String word1, String word2) {
        dp = new int[word1.length() + 1][word2.length() + 1];
        for (int[] a: dp)
            Arrays.fill(a,-1);
        return solve(word1, word2, 0, 0);
    }
 
    public int solve(String a, String b, int i, int j) {
        if (dp[i][j] != -1) return dp[i][j];
        
        if (i == a.length()) return dp[i][j] = b.length() - j;
        if (j == b.length()) return dp[i][j] = a.length() - i;
 
        if (a.charAt(i) == b.charAt(j))
            return dp[i][j] = solve(a, b, i+1, j+1);
        else
            return dp[i][j] = 1 + Math.min(solve(a,b,i+1,j), solve(a,b,i,j+1));
    }
}

Approach - Recursion

• Similar to longest common subsequence so what we would do is either we can delete from one or the other and our end case is if we reach end of first then we need to delete rest from the second and vice versa
• O(2^(m+n)), O(m+n) It is because of the call stack length or max depth that is m + n

class Solution {
    public int minDistance(String word1, String word2) {
        return solve(word1, word2, 0, 0);
    }
 
    public int solve(String a, String b, int i, int j) {
        if (i == a.length())
            return b.length() - j;
        if (j == b.length())
            return a.length() - i;
 
        if (a.charAt(i) == b.charAt(j))
            return solve(a, b, i+1, j+1);
        else
            return 1 + Math.min(solve(a,b,i+1,j), solve(a,b,i,j+1));
    }
}