Add an ArrayList of persons to the Person class.
[Persons_Comparator.git] / src / LevenshteinDistance.java
CommitLineData
ac6c3ea2
JB
1
2public class LevenshteinDistance {
3 /**
ac6c3ea2
JB
4 * @param a
5 * @param b
6 * @param c
7 * @return
8 */
9 private static int minimum(int a, int b, int c) {
10 return Math.min(Math.min(a, b), c);
11 }
12
13 /**
ac6c3ea2
JB
14 * @param lhs
15 * @param rhs
16 * @return
17 */
18 public static int computeLevenshteinDistance(CharSequence lhs, CharSequence rhs) {
19 int[][] distance = new int[lhs.length() + 1][rhs.length() + 1];
20
21 for (int i = 0; i <= lhs.length(); i++)
22 distance[i][0] = i;
23 for (int j = 1; j <= rhs.length(); j++)
24 distance[0][j] = j;
25
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));
32
33 return distance[lhs.length()][rhs.length()];
34 }
35}