public static int levenshteinDistance ( String o1 , String o2 ) { // Let o1 be the shorter one: if ( o1 . length ( ) > o2 . length ( ) ) { return levenshteinDistance ( o2 , o1 ) ; } final int l1 = o1 . length ( ) , l2 = o2 . length ( ) ; // Exploit that Java caches the hash code of strings: if ( l1 == l2 && o1 . hashCode ( ) == o2 . hashCode ( ) && o1 . equals ( o2 ) ) { return 0 ; } // Determine prefix and postfix lengths: final int prefix = prefixLen ( o1 , o2 ) ; if ( prefix == l1 || prefix == l2 ) { return Math . abs ( l1 - l2 ) ; } final int postfix = postfixLen ( o1 , o2 , prefix ) ; return // Prefix and postfix are a complete object: ( prefix + postfix == l1 || prefix + postfix == l2 ) ? Math . abs ( l1 - l2 ) : // // Exactly one char difference optimization: ( l1 == l2 && prefix + postfix + 1 == l1 ) ? 1 : // // Default case, compute levenshteinDistance ( o1 , o2 , prefix , postfix ) ; }
Levenshtein distance for two strings .