Minimum number of deletions and insertions

JavaView on GFG

Time: O(n*m)

Space: O(n*m)

Intuition

Minimum operations (delete from S1, insert into S1) to convert S1 to S2. LCS based.

Algorithm

1LCS length = L. Deletions = len(S1) - L. Insertions = len(S2) - L. Total = len(S1)+len(S2) - 2*L.

Common Pitfalls

•Equivalent to edit distance with only insert/delete. LCS gives common subsequence; remaining chars must be deleted/inserted.

Minimum number of deletions and insertions.java

Java

// Approach: Find LCS. Min operations = (n - LCS) deletions + (m - LCS) insertions.
// Time: O(n*m) Space: O(n*m)
import java.util.*;

class Solution {
    public int minOperations(String str1, String str2) {
        int m = str1.length();
        int n = str2.length();

        int[][] dp = new int[m + 1][n + 1];
        for (int[] row : dp)
            Arrays.fill(row, -1);

        int lcs = topDown(m, n, str1, str2, dp);

        return (m - lcs) + (n - lcs);
    }

    private int topDown(int i, int j, String text1, String text2, int[][] dp) {
        if (i == 0 || j == 0)
            return 0;

        if (dp[i][j] != -1)
            return dp[i][j];

        if (text1.charAt(i - 1) == text2.charAt(j - 1))
            return dp[i][j] = 1 + topDown(i - 1, j - 1, text1, text2, dp);

        return dp[i][j] = Math.max(topDown(i - 1, j, text1, text2, dp), topDown(i, j - 1, text1, text2, dp));
    }
}

Was this solution helpful?