2 public class LevenshteinDistance
{
9 private static int minimum(int a
, int b
, int c
) {
10 return Math
.min(Math
.min(a
, b
), c
);
18 public static int computeLevenshteinDistance(CharSequence lhs
, CharSequence rhs
) {
19 int[][] distance
= new int[lhs
.length() + 1][rhs
.length() + 1];
21 for (int i
= 0; i
<= lhs
.length(); i
++)
23 for (int j
= 1; j
<= rhs
.length(); j
++)
26 for (int i
= 1; i
<= lhs
.length(); i
++)
27 for (int j
= 1; j
<= rhs
.length(); j
++)
28 distance
[i
][j
] = minimum(
29 distance
[i
- 1][j
] + 1,
30 distance
[i
][j
- 1] + 1,
31 distance
[i
- 1][j
- 1] + ((lhs
.charAt(i
- 1) == rhs
.charAt(j
- 1)) ?
0 : 1));
33 return distance
[lhs
.length()][rhs
.length()];