-
Notifications
You must be signed in to change notification settings - Fork 1
/
StringDistances.java
70 lines (65 loc) · 1.63 KB
/
StringDistances.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
package Dynamic_Programming;
import java.util.Arrays;
public class StringDistances {
// https://en.wikipedia.org/wiki/Longest_common_subsequence_problem
public static int[] getLCS(int[] x, int[] y) {
int m = x.length;
int n = y.length;
int[][] lcs = new int[m + 1][n + 1];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (x[i] == y[j]) {
lcs[i + 1][j + 1] = lcs[i][j] + 1;
} else {
lcs[i + 1][j + 1] = Math.max(lcs[i + 1][j], lcs[i][j + 1]);
}
}
}
int cnt = lcs[m][n];
int[] res = new int[cnt];
for (int i = m - 1, j = n - 1; i >= 0 && j >= 0; ) {
if (x[i] == y[j]) {
res[--cnt] = x[i];
--i;
--j;
} else if (lcs[i + 1][j] > lcs[i][j + 1]) {
--j;
} else {
--i;
}
}
return res;
}
// https://en.wikipedia.org/wiki/Levenshtein_distance
public static int getLevensteinDistance(String a, String b) {
int m = a.length();
int n = b.length();
int[][] len = new int[m + 1][n + 1];
for (int i = 0; i <= m; i++) {
len[i][0] = i;
}
for (int j = 0; j <= n; j++) {
len[0][j] = j;
}
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (a.charAt(i) == b.charAt(j)) {
len[i + 1][j + 1] = len[i][j];
} else {
len[i + 1][j + 1] = 1 + Math.min(len[i][j], Math.min(len[i + 1][j], len[i][j + 1]));
}
}
}
return len[m][n];
}
// Usage example
public static void main(String[] args) {
int[] x = {1, 5, 4, 2, 3, 7, 6};
int[] y = {2, 7, 1, 3, 5, 4, 6};
int[] lcs = getLCS(x, y);
System.out.println(Arrays.toString(lcs));
String a = "abc";
String b = "ac";
System.out.println(getLevensteinDistance(a, b));
}
}