forked from shuang790228/GeekTime-MathLecture-JavaCode
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathLesson10_1.java
More file actions
105 lines (75 loc) · 2.78 KB
/
Lesson10_1.java
File metadata and controls
105 lines (75 loc) · 2.78 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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
public class Lesson10_1 {
/**
* @Description: 使用状态转移方程，计算两个字符串之间的编辑距离
* @param a-第一个字符串，b-第二个字符串
* @return int-两者之间的编辑距离
*/
public static int getStrDistance(String a, String b) {
if (a == null || b == null) return -1;
// 初始用于记录化状态转移的二维表
int[][] d = new int[a.length() + 1][b.length() + 1];
// 如果i为0，且j大于等于0，那么d[i, j]为j
for (int j = 0; j <= b.length(); j++) {
d[0][j] = j;
}
// 如果i大于等于0，且j为0，那么d[i, j]为i
for (int i = 0; i <= a.length(); i++) {
d[i][0] = i;
}
// 实现状态转移方程
// 请注意由于Java语言实现的关系，代码里的状态转移是从d[i, j]到d[i+1, j+1]，而不是从d[i-1, j-1]到d[i, j]。本质上是一样的。
for (int i = 0; i < a.length(); i++) {
for (int j = 0; j < b.length(); j++) {
int r = 0;
if (a.charAt(i) != b.charAt(j)) {
r = 1;
}
int first_append = d[i][j + 1] + 1;
int second_append = d[i + 1][j] + 1;
int replace = d[i][j] + r;
int min = Math.min(first_append, second_append);
min = Math.min(min, replace);
d[i + 1][j + 1] = min;
}
}
return d[a.length()][b.length()];
}
public static int getStrDistanceByThreshold(String a, String b, int threshold) {
if (a == null || b == null) return -1;
int minStrDist = Integer.MAX_VALUE;
// 初始用于记录化状态转移的二维表
int[][] d = new int[a.length() + 1][b.length() + 1];
// 如果i为0，且j大于等于0，那么d[i, j]为j
for (int j = 0; j <= b.length(); j++) {
d[0][j] = j;
}
// 如果i大于等于0，且j为0，那么d[i, j]为i
for (int i = 0; i <= a.length(); i++) {
d[i][0] = i;
}
// 实现状态转移方程
// 请注意由于Java语言实现的关系，代码里的状态转移是从d[i, j]到d[i+1, j+1]，而不是从d[i-1, j-1]到d[i, j]。本质上是一样的。
for (int i = 0; i < a.length(); i++) {
for (int j = 0; j < b.length(); j++) {
int r = 0;
if (a.charAt(i) != b.charAt(j)) {
r = 1;
}
int first_append = d[i][j + 1] + 1;
int second_append = d[i + 1][j] + 1;
int replace = d[i][j] + r;
int min = Math.min(first_append, second_append);
min = Math.min(min, replace);
d[i + 1][j + 1] = min;
if (min < minStrDist) minStrDist = min;
if (minStrDist > threshold) return -1;
}
}
return d[a.length()][b.length()];
}
public static void main(String[] args) {
// TODO Auto-generated method stub
System.out.println(Lesson10_1.getStrDistance("mouse", "mouuse"));
System.out.println(Lesson10_1.getStrDistanceByThreshold("mouse", "mouuse", 0));
}
}