47 lines
1.7 KiB
Java
47 lines
1.7 KiB
Java
public class Levenshtein{
|
|
public static int levenshtein(String s, String t){
|
|
/* if either string is empty, difference is inserting all chars
|
|
* from the other
|
|
*/
|
|
if(s.length() == 0) return t.length();
|
|
if(t.length() == 0) return s.length();
|
|
|
|
/* if first letters are the same, the difference is whatever is
|
|
* required to edit the rest of the strings
|
|
*/
|
|
if(s.charAt(0) == t.charAt(0))
|
|
return levenshtein(s.substring(1), t.substring(1));
|
|
|
|
/* else try:
|
|
* changing first letter of s to that of t,
|
|
* remove first letter of s, or
|
|
* remove first letter of t
|
|
*/
|
|
int a = levenshtein(s.substring(1), t.substring(1));
|
|
int b = levenshtein(s, t.substring(1));
|
|
int c = levenshtein(s.substring(1), t);
|
|
|
|
if(a > b) a = b;
|
|
if(a > c) a = c;
|
|
|
|
//any of which is 1 edit plus editing the rest of the strings
|
|
return a + 1;
|
|
}
|
|
|
|
public static void main(String[] args) {
|
|
String s1 = "kitten";
|
|
String s2 = "sitting";
|
|
System.out.println("distance between '" + s1 + "' and '"
|
|
+ s2 + "': " + levenshtein(s1, s2));
|
|
s1 = "rosettacode";
|
|
s2 = "raisethysword";
|
|
System.out.println("distance between '" + s1 + "' and '"
|
|
+ s2 + "': " + levenshtein(s1, s2));
|
|
StringBuilder sb1 = new StringBuilder(s1);
|
|
StringBuilder sb2 = new StringBuilder(s2);
|
|
System.out.println("distance between '" + sb1.reverse() + "' and '"
|
|
+ sb2.reverse() + "': "
|
|
+ levenshtein(sb1.reverse().toString(), sb2.reverse().toString()));
|
|
}
|
|
}
|