LeetCode 72. 编辑距离
原题链接
困难
作者:
Java小码农
,
2022-08-02 01:14:09
,
所有人可见
,
阅读 132
C++ 代码
class Solution {
public:
int minDistance(string a, string b) {
int n = a.size(), m = b.size();
a = ' ' + a, b = ' ' + b;
vector<vector<int>> f(n + 1, vector<int>(m + 1));
for (int i = 0; i <= n; i ++ ) f[i][0] = i;
for (int i = 1; i <= m; i ++ ) f[0][i] = i;
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= m; j ++ ) {
f[i][j] = min(f[i - 1][j], f[i][j - 1]) + 1;
int t = a[i] != b[j];
f[i][j] = min(f[i][j], f[i - 1][j - 1] + t);
}
return f[n][m];
}
};