Minimum Number Of Insertion And Deletion Geeks For Geeks

 class Solution

{

public int minOperations(String s1, String s2) 

{ 

    int n=s1.length();

    int m=s2.length();

    int p=cal(s1,s2,n,m);

    //System.out.println(p);

    return p;

} 

public int cal(String x, String y, int n, int m){

    int t[][]=new int[n+1][m+1];

    for(int i=0;i<n+1;i++){

        for(int j=0;j<m+1;j++){

            if(i==0 ||j==0){

                t[i][j]=0;

            }

        }

    }

    

    for(int i=1;i<n+1;i++){

        for(int j=1;j<m+1;j++){

            if(x.charAt(i-1)==y.charAt(j-1)){

                t[i][j]=t[i-1][j-1]+1;

            }

            else{

                t[i][j]=Integer.max(t[i-1][j],t[i][j-1]);

            }

        }

    }

    

    int c=t[n][m];

    

    int del=n-c;

    int ins=m-c;

    

    return del+ins;

    

}

}

APPROACH:

Here we have to convert String a to String b. The insertion and deletion from the string will be made of those characters which are not common in both. 

If we observe that we need to find the common elements between two strings and we can do that by LCS. Also before applying LCS we need to see whether this question belongs to LCS or not.

For being an LCS question it should be a question of DP. Here we have to find out the minimum number of operations and if any question some optimal solution is required then we need to think of DP. So clearly it's a Dp question and since we are not provided with choices either to take a particular character or not so it will not belong to the category of knapsack, Hence it's an LCS.

If we find out LCS and then remove the characters from string A which are not present in LCS then we get deletion value.

and similarly, if we find different characters between LCS and String b then we get insertion characters.

So In gist, If

LCS Length =  l;

String a length= x;

String b length=y;

Deletion: x-l;

Inseertion : y-l;

As LCS is common between String a and String b and its length l will always be less than x and y.  (Always l=<x and l=<y).

TIME:O(N*M)[Geeks For Geeks Time: 0.2/1.5]

SPACE: O(N*M)

Thanks For Reading.😇

"Share further to increase knowledge treasure.😊"