Minimum Operations to Make two strings Equal

The idea behind this code is that we check for the longest common subsequence(LCS) in both the strings and once we get it, we simply subtract the length of that LCS from both strings and add both the differences.
eg: str1 = “abcd” : str2 = “aed”
Here we have “ad” as LCS so in str1 we delete b,c which is 2
operations and we insert “e” in it which is another operation.
Hence total of 2+1=3 operations.
This can also be written as (str1-ad)+(str2-ad) or (str1+str2)-2*ad or (str1.len + str2.len)-2*LCS.len .

`public static int operationsCount(String s1, String s2) {

    int n=s1.length();
    int m=s2.length();
    int prev[]=new int[m+1];

    for(int ind1=1;ind1<=n;ind1++){
        int cur[]=new int[m+1];
    for(int ind2=1;ind2<=m;ind2++){
        if(s1.charAt(ind1-1)==s2.charAt(ind2-1))
            cur[ind2] = 1 + prev[ind2-1];
        else
            cur[ind2] = 0 + Math.max(prev[ind2],cur[ind2-1]);
    }
    prev= cur;
}

return (n+m)-2*prev[m];
}`

Enter fullscreen mode Exit fullscreen mode

原文链接：Minimum Operations to Make two strings Equal