Skip to content

Instantly share code, notes, and snippets.

@vaibhav-jani
Created January 24, 2019 10:47
Show Gist options
  • Select an option

  • Save vaibhav-jani/cce1aa7019f0aaa3f0dca5013999f839 to your computer and use it in GitHub Desktop.

Select an option

Save vaibhav-jani/cce1aa7019f0aaa3f0dca5013999f839 to your computer and use it in GitHub Desktop.
Levenshtein distance in java
// Find the Levenshtein distance
private int distance(String a, String b) {
a = a.toLowerCase();
b = b.toLowerCase();
int[] costs = new int[b.length() + 1];
for (int j = 0; j < costs.length; j++)
costs[j] = j;
for (int i = 1; i <= a.length(); i++) {
costs[0] = i;
int nw = i - 1;
for (int j = 1; j <= b.length(); j++) {
int cj = Math.min(1 + Math.min(costs[j], costs[j - 1]),
a.charAt(i - 1) == b.charAt(j - 1) ? nw : nw + 1);
nw = costs[j];
costs[j] = cj;
}
}
return costs[b.length()];
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment