LeetCode - Edit Distance

Given two words word1 and word2, find the minimum number of steps required to convert word1 to word2. (each operation is counted as 1 step.)

You have the following 3 operations permitted on a word:

a) Insert a character
b) Delete a character
c) Replace a character

 

Solution:

The following recurrence relations define the edit distance, d(s1,s2), of two strings s1 and s2:

d('', '') = 0               -- '' = empty string
d(s, '')  = d('', s) = |s|  -- i.e. length of s
d(s1+ch1, s2+ch2)
  = min( d(s1, s2) + if ch1=ch2 then 0 else 1 fi,
         d(s1+ch1, s2) + 1,
         d(s1, s2+ch2) + 1 )

The first two rules above are obviously true, so it is only necessary consider the last one. Here, neither string is the empty string, so each has a last character, ch1 and ch2 respectively. Somehow, ch1 and ch2 have to be explained in an edit of s1+ch1 into s2+ch2. If ch1 equals ch2, they can be matched for no penalty, i.e. 0, and the overall edit distance is d(s1,s2). If ch1 differs from ch2, then ch1 could be changed into ch2, i.e. 1, giving an overall cost d(s1,s2)+1. Another possibility is to delete ch1 and edit s1 into s2+ch2, d(s1,s2+ch2)+1. The last possibility is to edit s1+ch1 into s2 and then insert ch2, d(s1+ch1,s2)+1. There are no other alternatives. We take the least expensive, i.e. min, of these alternatives.

 

A two-dimensional matrix, m[0..|s1|,0..|s2|] is used to hold the edit distance values:

m[i,j] = d(s1[1..i], s2[1..j])

m[0,0] = 0
m[i,0] = i,  i=1..|s1|
m[0,j] = j,  j=1..|s2|

m[i,j] = min(m[i-1,j-1]
             + if s1[i]=s2[j] then 0 else 1 fi,
             m[i-1, j] + 1,
             m[i, j-1] + 1 ),  i=1..|s1|, j=1..|s2|

m[,] can be computed row by row. Row m[i,] depends only on row m[i-1,]. The time complexity of this algorithm is O(|s1|*|s2|). If s1 and s2 have a `similar' length, about `n' say, this complexity is O(n²), much better than exponential!

 

public int minDistance(String word1, String word2) {
    int m = word1.length(), n = word2.length();
    int[][] f = new int[m+1][n+1];
    for(int i=0; i<=m; i++) {
        f[i][0] = i;
        for(int j=0; j<=n; j++) {
            if(i==0) f[0][j] = j;
            else if(j!=0) f[i][j] = Integer.MAX_VALUE; //注意，其他元素初始化为INT_MAX
        }
    }

    for(int i=1; i<=m; i++) {
        for(int j=1; j<=n; j++) {
            int diff = (word1.charAt(i-1) != word2.charAt(j-1)) ? 1 : 0;
            f[i][j] = Math.min(f[i][j], f[i-1][j-1]+diff); //replace if cost=1
            f[i][j] = Math.min(f[i][j], f[i-1][j]+1); //delete
            f[i][j] = Math.min(f[i][j], f[i][j-1]+1); //insert
        }
    }
    return f[m][n];
}

 

Reference:

http://www.csse.monash.edu.au/~lloyd/tildeAlgDS/Dynamic/Edit/