src/LevenshteinDistance.java

   1
   2 public class LevenshteinDistance {
   3     /**
   4      *
   5      * @param a
   6      * @param b
   7      * @param c
   8      * @return
   9      */
  10     private static int minimum(int a, int b, int c) {
  11         return Math.min(Math.min(a, b), c);
  12     }
  13
  14     /**
  15      *
  16      * @param lhs
  17      * @param rhs
  18      * @return
  19      */
  20     public static int computeLevenshteinDistance(CharSequence lhs, CharSequence rhs) {
  21         int[][] distance = new int[lhs.length() + 1][rhs.length() + 1];
  22
  23         for (int i = 0; i <= lhs.length(); i++)
  24             distance[i][0] = i;
  25         for (int j = 1; j <= rhs.length(); j++)
  26             distance[0][j] = j;
  27
  28         for (int i = 1; i <= lhs.length(); i++)
  29             for (int j = 1; j <= rhs.length(); j++)
  30                 distance[i][j] = minimum(
  31                         distance[i - 1][j] + 1,
  32                         distance[i][j - 1] + 1,
  33                         distance[i - 1][j - 1] + ((lhs.charAt(i - 1) == rhs.charAt(j - 1)) ? 0 : 1));
  34
  35         return distance[lhs.length()][rhs.length()];
  36     }
  37 }