题解 | #计算字符串的编辑距离#
计算字符串的编辑距离
https://www.nowcoder.com/practice/3959837097c7413a961a135d7104c314
#include <iostream>
#include <vector>
using namespace std;
int main() {
string s,t;
cin>>s>>t;
vector<vector<int>> dp(s.size() + 1, vector<int>(t.size() + 1, 0));
for (int i = 1; i <= s.size(); i++) dp[i][0] = i;
for (int i = 1; i <= t.size(); i++) dp[0][i] = i;
for (int i = 1; i <= s.size(); i++){
for (int j = 1; j <= t.size(); j++){
if (s[i - 1] == t[j - 1]){
dp[i][j] = dp[i - 1][j - 1];
}
else {
dp[i][j] = min(dp[i - 1][j], min(dp[i][j - 1], dp[i - 1][j - 1])) + 1;
}
}
}
cout << dp[s.size()][t.size()];
}
// 64 位输出请用 printf("%lld")
查看13道真题和解析