Edit Distance

EditDistance.java

/*
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
*/
public int editDistance(String w1, String w2){
    if (w1 == null || w2 == null) throw new IllegalArgumentException("Input string cannot be null");    
    int n1 = w1.length(), n2 = w2.length();
    
    // f[i][j] stands for the minimum edit distance of  W1[0..i-1] and W2[0..j-1]
    int[][] f = new int[n1+1][n2+1];
    
    // Initialization
    for (int i=1; i<=len1; i++)
        f[i][0] = i;
    for (int j=1; j<=len2; j++)
        f[0][j] = j;
        
    for (int i=1; i<=len1; i++){
        for (int j=1; j<=len2; j++){
            f[i][j] = f[i-1][j-1] + (w1.charAt(i-1) == w2.charAt(j-1) ? 0 : 1 );
            f[i][j] = Math.min(f[i][j], Math.min(f[i-1][j], f[i][j-1]) + 1);
        }
    }
    return f[len1][len2];
}