Skip to content

Instantly share code, notes, and snippets.

@i-tu
Last active Aug 29, 2015
Embed
What would you like to do?
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