src/LevenshteinDistance.java

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