题目ref
经典的dp问题,分析可知,操作和顺序无关,所有只考虑按照顺序在单词末尾操作,同时不考虑对一个字符反复增删(该情况不是最优的方案,因为操作一次就行)。
分为6个情况,串a的增/删/替,串b的增/删/替。其中
f[i][j] 表示 a的第i个字符 和 b的第j个字符的编辑距离
串a增:表示 a[1~i] 和 b[1~j-1] 是已经匹配的,此时为 f[i]][j-1] + 1;
串a减: 表示 a[1~i-1] 和 b[1~j] 是已经匹配的,此时为 f[i-1]][j] + 1;
串a[i]替换成串b[j]:表示 a[1~i-1] 和 b[1~j-1] 是已经匹配的,此时为 f[i-1]][j-1] + a[i] == b[j];
串b增:表示 a[1~i-1] 和 b[1~j] 是已经匹配的,此时为 f[i-1]][j] + 1;
串b减: 表示 a[1~i] 和 b[1~j-1] 是已经匹配的,此时为 f[i]][j-1] + 1;
串a[i]替换成串b[j]:表示 a[1~i-1] 和 b[1~j-1] 是已经匹配的,此时为 f[i-1]][j-1] + a[i] == b[j];
C++ 代码
class Solution {
public:
int minDistance(string word1, string word2) {
int m = word1.size(), n = word2.size();
vector<vector<int>> f(m+1, vector<int>(n+1, 0));
for(int i=0; i<=m; ++i)f[i][0] = i;
for(int j=0; j<=n; ++j)f[0][j] = j;
for(int i=1; i<=m; ++i) {
for(int j=1; j<=n; ++j) {
f[i][j] = min(f[i-1][j-1], min(f[i-1][j], f[i][j-1])) + 1;
if(word1[i-1] == word2[j-1]) {
f[i][j] = min(f[i][j], f[i-1][j-1]);
}
}
}
return f[m][n];
}
};
CSP-J 初赛结束后做是吧(