Edit Distance

public class EditDist {
  public enum METHOD {
    KEEP, CHANGE, INSERT, DELETE;
  }

  private static class Solution {
    public int price;
    public METHOD method;
    public Solution() {}
  }

  private static Solution[][] solutions;

  /** Returns how many changes (delete, change, insert) have to be done to get from s1 to s2 */
  public static int distance(String s1, String s2) {
    return distance(s1.toCharArray(), s2.toCharArray(), s1.length()-1, s2.length()-1);
  }

  public static int distance(char[] s1, char[] s2, int i, int j) {
    if (solutions == null) {
      solutions = new Solution[s1.length][s2.length];
      for (int a = 0; a<s1.length; a++)
        for (int b = 0; b<s2.length; b++)
          solutions[a][b] = new Solution();
    }

    if (i < 0) return j+1;
    if (j < 0) return i+1;

    if (solutions[i][j].price != 0)
      return solutions[i][j].price;

    int changePrice = distance(s1, s2, i-1, j-1) + (s1[i] == s2[j] ? 0 : 1);
    int insertPrice = distance(s1, s2, i, j-1) + 1;
    int deletePrice = distance(s1, s2, i-1, j) + 1;

    solutions[i][j].price = Math.min(deletePrice, Math.min(changePrice, insertPrice));

    if (solutions[i][j].price == deletePrice)
      solutions[i][j].method = METHOD.DELETE;
    else if (solutions[i][j].price == insertPrice)
      solutions[i][j].method = METHOD.INSERT;
    else if (solutions[i][j].price == changePrice && s1[i] != s2[j])
      solutions[i][j].method = METHOD.CHANGE;
    else
      solutions[i][j].method = METHOD.KEEP;

    return solutions[i][j].price;
  }

  public static String strategy() {
    StringBuffer sb = new StringBuffer();

    int i = solutions.length-1;
    int j;

    if (i >= 0) j = solutions[0].length - 1;
    else j = -1;

    while (i >= 0 && j >= 0) {
      if (i < 0) {
        for (int k=0; k<j; k++)
          sb.insert(0, METHOD.DELETE.toString() + ", " );
        return sb.toString();
      }

      if (j < 0) {
        for (int k=0; k<i; k++)
          sb.insert(0, METHOD.INSERT.toString() + ", " );
        return sb.toString();
      }

      METHOD m = solutions[i][j].method;
      sb.insert(0, m.toString() + ", ");

      if (m == METHOD.KEEP || m == METHOD.CHANGE) {
        i--;
        j--;
      }
      else if (m == METHOD.INSERT)
        j--;
      else if (m == METHOD.DELETE)
        i--;
    }

    return sb.toString();
  }

  public static void main (String [] args) {
    System.out.println(distance("diesen morgen haben sieben schwaben einen gelben hasen gesehen", "this morning have seven schwabs a yellow hare seen"));
    System.out.println(strategy());
/*
   
> java EditDist
 28
 CHANGE, INSERT, KEEP, DELETE, KEEP, DELETE, DELETE, KEEP, KEEP, KEEP, KEEP, CHANGE, CHANGE, KEEP, INSERT, KEEP, KEEP, KEEP, CHANGE, KEEP, DELETE, KEEP, KEEP, DELETE, KEEP, CHANGE, KEEP, KEEP, KEEP, KEEP, KEEP, KEEP, KEEP, KEEP, KEEP, CHANGE, DELETE, KEEP, CHANGE, DELETE, DELETE, DELETE, DELETE, KEEP, CHANGE, KEEP, KEEP, CHANGE, CHANGE, CHANGE, KEEP, KEEP, KEEP, CHANGE, KEEP, DELETE, KEEP, DELETE, DELETE, KEEP, KEEP, DELETE, KEEP, KEEP, 
 
*/
  }

}