How can you use dynamic programming to solve the Edit Distance problem? Implement the solution.?

The Edit Distance problem involves finding the minimum number of edits (insertion, deletion, or substitution) needed to transform one string into another. This problem can be solved using dynamic programming.

The dynamic programming approach for the Edit Distance problem involves building a table that stores the minimum number of edits required to transform prefixes of the two strings being compared. We build up the solution for larger prefixes by using solutions to smaller prefixes.

Let’s consider an example where we want to transform the word "kitten" to "sitting". We can solve this problem using dynamic programming as follows:

1. We create a table with (m+1) rows and (n+1) columns where m and n are the lengths of the two strings being compared. In our case, the table will have 7 rows and 7 columns.

2. We fill the first row and column of the table with values representing the number of edits needed to transform an empty string to the corresponding prefix of the other string. For example, the first row will be filled with values 0, 1, 2, 3, 4, 5, 6 as we need 0, 1, 2, 3, 4, 5, and 6 edits to convert an empty string to the prefix of the string "sitting" of length 0, 1, 2, 3, 4, 5, and 6.

3. We fill the rest of the table using the following recurrence relation:

    if word1[i-1] == word2[j-1]:
        dp[i][j] = dp[i-1][j-1]
    else:
        dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1

The above code compares each character of both strings and calculates the minimum cost by:

    - 1 gap insertion = dp[i-1][j]+1
    - 1 gap deletion  = dp[i][j-1]+1
    - 1 substitution = dp[i-1][j-1]+1

4. The final value present in the bottom right-most cell of the table represents the minimum number of edits required to transform the first string to the second string.

Heres the Java implementation of the algorithm:

public static int editDistance(String word1, String word2) {
    int m = word1.length();
    int n = word2.length();
    
    int[][] dp = new int[m+1][n+1];
    
    // fill the first row and column of the table
    for(int i=0; i<=m; i++) {
        dp[i][0] = i;
    }
    
    for(int i=0; i<=n; i++) {
        dp[0][i] = i;
    }
    
    // fill the rest of the table
    for(int i=1; i<=m; i++) {
        for(int j=1; j<=n; j++) {
            if(word1.charAt(i-1) == word2.charAt(j-1)) {
                dp[i][j] = dp[i-1][j-1];
            } else {
                dp[i][j] = Math.min(dp[i-1][j], Math.min(dp[i][j-1], dp[i-1][j-1])) + 1;
            }
        }
    }
    
    // return the final value in the table  
    return dp[m][n];
}

Let’s test the algorithm with the example we used earlier:

String word1 = "kitten";
String word2 = "sitting";
int result = editDistance(word1, word2);

System.out.println(result); // output: 3

The output is 3 which means it will take 3 edits to transform "kitten" to "sitting".