Algorithm Implement of Strings -- Edit Distance

/**
 * Algorithm Implementations in Java
 * created on Jul 29, 2011
 * ended it on Aug 1, 2011
 *
 */
package org.mht.strings;

public class LevenshteinDistance {

    public LevenshteinDistance() { }

    public static int levenshteinDistance(String source, String target) {

        int m = source.length();
        int n = target.length();

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

        for (int i = 0; i <= m; i++)
            distance[i][0] = i;
        for (int j = 0; j <= n; j++)
            distance[0][j] = j;

    //    System.out.println("distance[0][2] is " + distance[0][2]);

        for (int i = 1; i <= m; i++)
            for (int j = 1; j <= n; j++)
                distance[i][j] = minimum(distance[i-1][j]+1, minimum(distance[i][j-1]+1, distance[i-1][j-1]+
                            ((source.charAt(i-1) == target.charAt((j-1)) ? 0 : 1))));
        return distance[m][n];
        }

    public static int minimum(int dist1, int dist2) {
        if (dist1 >= dist2)
            return dist2;
        else
            return dist1;
        }

}///:~

/**
 * Algorithm psudocode from:
 *
 * int LevenshteinDistance(char s[1..m], char t[1..n]){
  // for all i and j, d[i,j] will hold the Levenshtein distance between
  // the first i characters of s and the first j characters of t;
  // note that d has (m+1)x(n+1) values
  declare int d[0..m, 0..n]

  for i from 0 to m
    d[i, 0] := i // the distance of any first string to an empty second string
  for j from 0 to n
    d[0, j] := j // the distance of any second string to an empty first string

  for j from 1 to n
  {
    for i from 1 to m
    {
      d[i, j] := minimum(
                     d[i-1, j] + 1,  // a deletion
                     d[i, j-1] + 1,  // an insertion
                     d[i-1, j-1] +  ? 0 : 1 // a substitution, 0 for same , otherwise 1
                   )
    }
  }

  return d[m,n]
}
 */