-
Notifications
You must be signed in to change notification settings - Fork 0
/
EditDistance.cpp
126 lines (120 loc) · 3.82 KB
/
EditDistance.cpp
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
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
/*
_ooOoo_
o8888888o
88" . "88
(| -_- |)
O\ = /O
____/`---'\____
.' \\| |// `.
/ \\||| : |||// \
/ _||||| -:- |||||- \
| | \\\ - /// | |
| \_| ''\---/'' | |
\ .-\__ `-` ___/-. /
___`. .' /--.--\ `. . __
."" '< `.___\_<|>_/___.' >'"".
| | : `- \`.;`\ _ /`;.`/ - ` : | |
\ \ `-. \_ __\ /__ _/ .-` / /
======`-.____`-.___\_____/___.-`____.-'======
`=---='
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
God Bless Me BUG Free Forever
*/
/***
* DP
* 定义d[i, j] 表示word1的前i个字符和word2的前j个字符的最小编辑距离
* 则i字符串有3种途径变为j
* / d[i-1, j-1], word1[i] == word2[j]
* / d[i-1, j] + 1, delete, word2删掉i字符
* d[i, j] = - d[i, j-1] + 1, insert, word2插入j字符
* \ d[i-1, j-1] + 1, replace, word1[i] != word2[j]
* 初始化 d[0, j] = j; d[i, 0] = i
* 注：字符长度从0~n，所以dp[]长 n+1
***/
/*
class Solution {
public:
int minDistance(string word1, string word2) {
int n1 = word1.size();
int n2 = word2.size();
vector<vector<int> > dp(n1+1, vector<int>(n2+1, 0));
for (int i = 0; i <= n1; ++i)
dp[i][0] = i;
for (int j = 0; j <= n2; ++j)
dp[0][j] = j;
for (int i = 1; i <= n1; ++i)
{
for (int j = 1; j <= n2; ++j)
{
if (word1[i-1] == word2[j-1]) // caution: index i-1
dp[i][j] = dp[i-1][j-1];
else
dp[i][j] = min(min(dp[i][j-1], dp[i-1][j]), dp[i-1][j-1]) + 1;
}
}
return dp[n1][n2];
}
};
*/
/***
* 法2：DP + 滚动数组
* 只需要记录相邻两行数据，用一维数组实现
* 需要记录的值d[i, j-1] d[i-1, j] d[i-1, j-1]
* 前两个都可以复用数组，d[i-1, j-1]需要额外的变量记录
* upper_left upper
* dp[j-1] dp[j]
***/
class Solution {
public:
int minDistance(string word1, string word2) {
int n1 = word1.size();
int n2 = word2.size();
vector<int> dp(n2+1, 0); // rolling array
for (int j = 0; j <= n2; ++j)
dp[j] = j;
for (int i = 1; i <= n1; ++i)
{
int upper_left = dp[0]; // caution!!! save dp[i-1][j-1]
dp[0] = i; // init dp[i][0]
for (int j = 1; j <= n2; ++j)
{
int upper = dp[j]; // upperleft for next j
if (word1[i-1] == word2[j-1])
dp[j] = upper_left;
else
dp[j] = min(min(dp[j], dp[j-1]), upper_left) + 1;
upper_left = upper; // update for next j
}
}
return dp[n2];
}
};
// 注意dp数组的长度 和 初始化
// dp[i][j] 表示 word1[0, i) 和 word2[0, j) 的编辑距离
// / dp[i-1]dp[j-1], word1[i] == word2[j]
// dp[i][j] =
// \ min{dp[i-1][j], dp[i][j-1], dp[i-1][j-1]} + 1, word1[i] != word2[j]
class Solution {
public:
int minDistance(string word1, string word2) {
const int n = word1.size();
const int m = word2.size();
if (0 == n)
return m;
if (0 == m)
return n;
vector<vector<int> > dp(n, vector<int>(m, 0));
for (int i = 0; i < n; ++i)
{
for (int j = 0; j < m; ++j)
{
if (word1[i] == word2[j])
dp[i][j] = (0 == i) ? j : ((0 == j) ? i : dp[i-1][j-1]);
else
dp[i][j] = min(min((0 == i) ? j+1 : dp[i-1][j], (0 == j) ? i+1 : dp[i][j-1]),
(0 == i) ? j : ((0 == j) ? i : dp[i-1][j-1])) + 1;
}
}
return dp[n-1][m-1];
}
};