Edit Distance

In dynamic programming, the Edit Distance is a measure of the similarity between two strings. It gives us the minimum number of operations (insertions, deletions, and substitutions) required to transform one string into another.

For example, let's consider two strings: "developer" and "designer". The edit distance between these two strings is 3. We can transform the string "developer" into "designer" by substituting 'v' with 's', 'e' with 'i', and 'r' with 'g'.

To calculate the edit distance between two strings, we can use a dynamic programming approach. We can create a 2D array dp of size (m+1) x (n+1), where m and n are the lengths of the two strings.

We initialize the first row of dp with values from 0 to m and the first column with values from 0 to n. This represents the edit distance between an empty string and a substring of the first string, and vice versa.

Then, we iterate through the characters of the two strings. If the characters are the same, we copy the value from dp[i-1][j-1] to dp[i][j]. Otherwise, we take the minimum of the three adjacent cells (dp[i-1][j-1], dp[i][j-1], and dp[i-1][j]) and add 1, representing the cost of the respective operation.

Finally, the value at dp[m][n] represents the edit distance between the two strings.

Here's the Java code to calculate the edit distance:

1<<code>>

xxxxxxxxxx

}

class Main {

  public static void main(String[] args) {

    String str1 = "developer";

    String str2 = "designer";

    int distance = editDistance(str1, str2);

    System.out.println("Edit Distance between " + str1 + " and " + str2 + ": " + distance);

  }

​

  public static int editDistance(String word1, String word2) {

    int m = word1.length();

    int n = word2.length();

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

​

    for (int i = 0; i <= m; i++) {

      dp[i][0] = i;

    }

​

    for (int j = 0; j <= n; j++) {

      dp[0][j] = j;

    }

​

    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] = 1 + Math.min(dp[i - 1][j - 1], Math.min(dp[i][j - 1], dp[i - 1][j]));

        }

      }