forked from xiaoningning/java-algorithm-2010
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathWordEditDistance.java
More file actions
47 lines (36 loc) · 1.5 KB
/
WordEditDistance.java
File metadata and controls
47 lines (36 loc) · 1.5 KB
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
/*
** Dynamic Programming, very similar to longest common substring question
**
** dis[i,j] means the distance from transform s1s2..si to t1t2...tj
** then the value of dis[i,j] should the minimus value of following:
** d[i-1, j] + deletion (just delete si to have d[i-1, j] situation)
** d[i, j-1] + insertion (base on d[i, j-1], insert tj to s become d[i, j])
** d[i-1, j-1]+substitution (base on d[i-1,j-1], replace si with tj become d[i, j])
*/
public class WordEditDistance {
public static void main(String[] args) {
wordEditDistance("aabc", "aacc");
wordEditDistance("aabbcc", "aabb");
wordEditDistance("aabac", "abac");
wordEditDistance("algorithm", "altruistic");
}
public static void wordEditDistance(String source, String target) {
int sLen = source.length();
int tLen = target.length();
int[][] dist = new int[sLen + 1][tLen + 1];
int i = 0, j = 0;
for (i = 1; i < sLen + 1; ++i)
dist[i][0] = i;
for (j = 1; j < tLen + 1; ++j)
dist[0][j] = j;
for (i = 1; i < sLen + 1; ++i) {
for (j = 1; j < tLen + 1; ++j) {
int d1 = dist[i - 1][j] + 1;
int d2 = dist[i][j - 1] + 1;
int d3 = dist[i - 1][j - 1] + ((source.charAt(i - 1) == target.charAt(j - 1)) ? 0 : 1);
dist[i][j] = Math.min(d1, Math.min(d2, d3));
}
}
System.out.println(source + "->" + target + ": " + dist[sLen][tLen]);
}
}