Commit | Line | Data |
---|---|---|
ac6c3ea2 JB |
1 | |
2 | public class LevenshteinDistance { | |
3 | /** | |
4 | * | |
5 | * @param a | |
6 | * @param b | |
7 | * @param c | |
8 | * @return | |
9 | */ | |
10 | private static int minimum(int a, int b, int c) { | |
11 | return Math.min(Math.min(a, b), c); | |
12 | } | |
13 | ||
14 | /** | |
15 | * | |
16 | * @param lhs | |
17 | * @param rhs | |
18 | * @return | |
19 | */ | |
20 | public static int computeLevenshteinDistance(CharSequence lhs, CharSequence rhs) { | |
21 | int[][] distance = new int[lhs.length() + 1][rhs.length() + 1]; | |
22 | ||
23 | for (int i = 0; i <= lhs.length(); i++) | |
24 | distance[i][0] = i; | |
25 | for (int j = 1; j <= rhs.length(); j++) | |
26 | distance[0][j] = j; | |
27 | ||
28 | for (int i = 1; i <= lhs.length(); i++) | |
29 | for (int j = 1; j <= rhs.length(); j++) | |
30 | distance[i][j] = minimum( | |
31 | distance[i - 1][j] + 1, | |
32 | distance[i][j - 1] + 1, | |
33 | distance[i - 1][j - 1] + ((lhs.charAt(i - 1) == rhs.charAt(j - 1)) ? 0 : 1)); | |
34 | ||
35 | return distance[lhs.length()][rhs.length()]; | |
36 | } | |
37 | } |