Skip to content

Instantly share code, notes, and snippets.

Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save RaminHAL9001/7fbf1e2c9080ed50c2ae to your computer and use it in GitHub Desktop.
Save RaminHAL9001/7fbf1e2c9080ed50c2ae to your computer and use it in GitHub Desktop.
public static int damLevDist(String A, String B) {
StringBuilder builder = new StringBuilder();
builder.append(" ");
A = A.toLowerCase(); B = B.toLowerCase();
int alen = A.length(), blen = B.length();
int maxdist = alen + blen;
int alphabet[] = new int[127];
for (int i = 0; i < alphabet.length; ++i) {
alphabet[i] = 0;
}
int H[][] = new int[alen + 2][blen + 2];
H[0][0] = maxdist;
for (int i = 0; i < alen; ++i) {
H[i][0] = maxdist;
H[i][1] = i;
}
for (int i = 0; i < blen; ++i) {
H[0][i] = maxdist;
H[1][i] = i;
builder.append(" ");
builder.append(B.charAt(i));
}
builder.append('\n');
for (int a = 2; a < alen + 2; ++a) {
int lastMatchIndex = 0;
char ca = A.charAt(a-2);
builder.append(ca);
builder.append(' ');
for (int b = 2; b < blen + 2; ++b) {
char cb = B.charAt(b-2);
int row = alphabet[cb];
int col = lastMatchIndex;
int cost = ca ==cb ? 0 : 1;
if (cost == 0) {
lastMatchIndex = b;
}
int w = min(
H[a-1][b-1] + cost,
H[a][b-1] + 1,
H[a-1][b] + 1,
H[row][col] + (a-2-row) + 1 + (b-2-col)
);
H[a][b] = w;
if (w <= 9) { builder.append(' '); }
if (w <= 99) { builder.append(' '); }
builder.append(String.valueOf(w));
}
builder.append('\n');
alphabet[ca] = a-1;
}
System.out.println(builder);
return H[alen+1][blen+1];
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment