Skip to content

Instantly share code, notes, and snippets.

@i-tu
Last active August 29, 2015 14:09
Show Gist options
  • Save i-tu/7499f04eb7eebe84aa2d to your computer and use it in GitHub Desktop.
Save i-tu/7499f04eb7eebe84aa2d to your computer and use it in GitHub Desktop.
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,
*/
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment