class CollectionsUtil {

  public static int getEditDistance2Lists(List<? extends Object> list1,
      List<? extends Object> list2) {
    // For all i and j, d[i][j] will hold the Levenshtein (edit) 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.
    int[][] d = new int[list1.size() + 1][list2.size() + 1];

    for (int i = 0; i < list1.size() + 1; i++) {
      // the distance of any first string to an empty second string
      // (transforming the string of the first i characters of s into
      // the empty string requires i deletions)
      d[i][0] = i;
    }
    for (int i = 0; i < list2.size() + 1; i++) {
      // the distance of any second string to an empty first string
      d[0][i] = i;
    }
    for (int j = 1; j < list2.size() + 1; j++) {
      for (int i = 1; i < list1.size() + 1; i++) {
        if (list1.get(i - 1).equals(list2.get(j - 1))) {
          // no operation required
          d[i][j] = d[i - 1][j - 1];
        } else {
          // d[i][j] is the minimum between a deletion, an insertion, or a
          // substitution
          d[i][j] = Math.min(d[i - 1][j] + 1,
              Math.min(d[i][j - 1] + 1, d[i - 1][j - 1] + 1));
        }
      }
    }
    return d[list1.size()][list2.size()];
  }

}