public class LevenshteinDistance {
  private static int minimum(int a, int b, int c) {
    return Math.min(Math.min(a, b), c);
  }

  public static int distance(String str1, String str2, long maximumDistance) {
    boolean brokeMax = false;
    int rowMinimum;
    int cost;
    String longestString = (str1.length() > str2.length()) ? str1 : str2;
    String shortestString = (str1.length() > str2.length()) ? str2 : str1;

    if (shortestString.equals(longestString)) { 
      return 0;
    } else if (longestString.length() - shortestString.length() > maximumDistance) {
      return longestString.length();
    } else if (shortestString.length() == 0 || longestString.length() == 0) {
      return longestString.length();
    }

    int[] workingGrid = new int[shortestString.length() + 1];
    int[] calculationGrid = new int[shortestString.length() + 1];
    int[] tempGrid;

    for (int i = 0; i <= shortestString.length(); i++) {
      calculationGrid[i] = i;
    }

    for (int i = 1; i <= longestString.length(); i++) {
      rowMinimum = workingGrid[0] = calculationGrid[0] + 1;

      for (int j = 1; j <= shortestString.length(); j++) {
        cost = (shortestString.charAt(j-1) == longestString.charAt(i-1)) ? 0 : 1;
        workingGrid[j] = minimum(calculationGrid[j]+1, workingGrid[j-1]+1, calculationGrid[j-1]+cost);
        rowMinimum = (workingGrid[j] < rowMinimum) ? workingGrid[j] : rowMinimum;
      }

      if (rowMinimum > maximumDistance) { 
        brokeMax = true;
        break;
      }

      tempGrid = workingGrid;
      workingGrid = calculationGrid;
      calculationGrid = tempGrid;
    }

    return brokeMax ? longestString.length() : calculationGrid[shortestString.length()];
  }

  public static int distance(String str1, String str2) {
    return distance(str1, str2, 9999);
  }

  public static float normalized_distance(String str1, String str2) {
   return normalized_distance(str1, str2, 9999); 
  }

  public static float normalized_distance(String str1, String str2, long maximumDistance) {
    int maxStringLength = (str1.length() > str2.length()) ? str1.length() : str2.length();
    if(maxStringLength == 0) {
      return 0;
    }
    return distance(str1, str2, maximumDistance) / (float)maxStringLength;
  }
}