Edit Distance in Java

In computer science, edit distance is a way of quantifying how dissimilar two strings (e.g., words) are to one another by counting the minimum number of operations required to transform one string into the other.
Let dp[i][j] stands for the edit distance between two strings with length i and j, i.e., word1[0,...,i-1] and word2[0,...,j-1].
There is a relation between dp[i][j] and dp[i-1][j-1]. Let's say we transform from one string to another. 

1. if x == y, then dp[i][j] == dp[i-1][j-1]
2. if x != y, and we insert y for word1, then dp[i][j] = dp[i][j-1] + 1
3. if x != y, and we delete x for word1, then dp[i][j] = dp[i-1][j] + 1
4. if x != y, and we replace x with y for word1, then dp[i][j] = dp[i-1][j-1] + 1
5. When x!=y, dp[i][j] is the min of the three situations.

Initial condition:
dp[i][0] = i, dp[0][j] = j

public static int minDistance(String word1, String word2) {
 int len1 = word1.length();
 int len2 = word2.length();
 
 // len1+1, len2+1, because finally return dp[len1][len2]
 int[][] dp = new int[len1 + 1][len2 + 1];
 
 for (int i = 0; i <= len1; i++) {
  dp[i][0] = i;
 }
 
 for (int j = 0; j <= len2; j++) {
  dp[0][j] = j;
 }
 
 //iterate though, and check last char
 for (int i = 0; i < len1; i++) {
  char c1 = word1.charAt(i);
  for (int j = 0; j < len2; j++) {
   char c2 = word2.charAt(j);
 
   //if last two chars equal
   if (c1 == c2) {
    //update dp value for +1 length
    dp[i + 1][j + 1] = dp[i][j];
   } else {
    int replace = dp[i][j] + 1;
    int insert = dp[i][j + 1] + 1;
    int delete = dp[i + 1][j] + 1;
 
    int min = replace > insert ? insert : replace;
    min = delete > min ? min : delete;
    dp[i + 1][j + 1] = min;
   }
  }
 }
 
 return dp[len1][len2];
}

From http://www.geeksforgeeks.org/dynamic-programming-set-5-edit-distance/

The time complexity of dynamic programming method is O(mn) as we need to construct the table fully. The space complexity is also O(mn). If we need only the cost of edit, we just need O(min(m, n)) space as it is required only to keep track of the current row and previous row.

Usually the costs D, I and R are not same. In such case the problem can be represented as an acyclic directed graph (DAG) with weights on each edge, and finding shortest path gives edit distance.

Read full article from Edit Distance in Java