Skip to content

Instantly share code, notes, and snippets.

@gabhi
Created April 24, 2014 06:16
Show Gist options
  • Save gabhi/11243437 to your computer and use it in GitHub Desktop.
Save gabhi/11243437 to your computer and use it in GitHub Desktop.
Levenshtein Edit Distance Algorithm in Java
public static int distance(String s1, String s2){
int edits[][]=new int[s1.length()+1][s2.length()+1];
for(int i=0;i<=s1.length();i++)
edits[i][0]=i;
for(int j=1;j<=s2.length();j++)
edits[0][j]=j;
for(int i=1;i<=s1.length();i++){
for(int j=1;j<=s2.length();j++){
int u=(s1.charAt(i-1)==s2.charAt(j-1)?0:1);
edits[i][j]=Math.min(
edits[i-1][j]+1,
Math.min(
edits[i][j-1]+1,
edits[i-1][j-1]+u
)
);
}
}
return edits[s1.length()][s2.length()];
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment