DP12_StringConversion.java

/*
* This Problem Is Very Similar To Edit Distance Problem Where We Have To Convert 'str1' --> 'str2'.......
* In String Conversion Problem , We Will Be Given 2 String str1 & str2 , We Have To Find Minimum Number
Of Operations Required To Convert String 'str1' --> String 'str2'.....
* The 2 Operations Permitted To Be Applied On A Word Are : -
--> Insert A Character In String 'str1'......
--> Delete A Character From String 'str1'......
* We Have To Tell The No Of Insert & Delete Operations To Convert 'str1' --> 'str2'......

    --> 'str1' --> LCS ::: This Will Determine The No Of Deletions Required For String Conversion Of 'str1' --> 'str2'.....
    --> LCS --> 'str2' ::: This Will Determine The No Of Insersion Required For String Conversion Of 'str1' --> 'str2'.....
*/

public class DP12_StringConversion {

    public static int LCS_DP_Tab(String str1, String str2, int m, int n) { // O(m*n)......
        int DP_Tab[][] = new int[m + 1][n + 1];
        // DP[i][j] -> LCS Value For first-(i) char Of 'str1'
        // And first-(j) char Of 'str2'.......

        // LCS Value Will Be 0 When Length Of 'str1' OR 'str2' Is 0.....
        for (int i = 0; i < m + 1; i++) { // To Initialize Col=0 With LCS Value=0......
            DP_Tab[i][0] = 0;
        }
        for (int i = 0; i < n + 1; i++) { // To Initialize Row=0 With LCS Value=0......
            DP_Tab[0][i] = 0;
        }

        for (int i = 1; i < (m + 1); i++) {
            for (int j = 1; j < (n + 1); j++) {
                char c1 = str1.charAt(i - 1); // Last Character Of String 'str1'....
                char c2 = str2.charAt(j - 1); // Last Character Of String 'str2'....

                if (c1 == c2) { // When Last Char Of Both String Is Same.....
                    DP_Tab[i][j] = DP_Tab[i - 1][j - 1] + 1;
                } else {
                    // Last Char Of 2 String Is Not Same.....
                    int ans1 = DP_Tab[i - 1][j]; // LCS Value For 'str1-c1' And 'str2'.....
                    int ans2 = DP_Tab[i][j - 1]; // LCS Value For 'str1' And 'str2-c2'.....
                    DP_Tab[i][j] = Math.max(ans1, ans2);
                }
            }
        }
        return DP_Tab[m][n];
    }

    public static void StringConversion(String str1, String str2) {
        int m = str1.length(); // Length Of String 'str1'.......
        int n = str2.length(); // Length Of String 'str2'.......
        int LCS = LCS_DP_Tab(str1, str2, m, n); // Length Of LCS Of String 'str1' & 'str2'.......

        int Insert_Operations = n - LCS; // Insert Operations ::: 'str2'-LCS.......
        int Delete_Operations = m - LCS; // Delete Operations ::: 'str1'-LCS.......

        System.out.println(
                "INSERT OPERATIONS REQUIRED TO CONVERT '" + str1 + "' TO '" + str2 + "' IS ::: " + Insert_Operations);
        System.out.println(
                "DELETE OPERATIONS REQUIRED TO CONVERT '" + str1 + "' TO '" + str2 + "' IS ::: " + Delete_Operations);
    }

    public static void main(String args[]) {
        String str1 = "abcdef";
        String str2 = "aceg";
        StringConversion(str1, str2);
    }
}