题目描述
设A和B是两个字符串。我们要用最少的字符操作次数，将字符串A转换为字符串B。这里所说的字符操作共有三种：
1、删除一个字符；
2、插入一个字符；
3、将一个字符改为另一个字符；
！皆为小写字母！
输入格式
第一行为字符串A；第二行为字符串B；字符串A和B的长度均小于2000。
输出格式
只有一个正整数，为最少字符操作次数。
输入输出样例
输入
sfdqxbw
gfdgw
输出
4
AC代码
#include <bits/stdc++.h>
using namespace std;
int edit[2002][2002] = {};
int min3(int a, int b, int c) {
return min(min(a, b), c);
}
int Levenshtein_Distance(string a, string b) {
int lenA = a.length(), lenB = b.length();
for (int i = 1; i <= lenA; i++) {
edit[i][0] = i;
}
for (int j = 1; j <= lenB; j++) {
edit[0][j] = j;
}
for (int i = 1; i <= lenA; i++) {
for (int j = 1; j <= lenB; j++) {
edit[i][j] = min3(edit[i - 1][j] + 1, edit[i][j - 1] + 1,
edit[i - 1][j - 1] + (a[i] != b[j]));
//删除，添加，修改三种方法中选择一个距离最小值
}
}
return edit[lenA][lenB];
}
int main() {
string a, b;
cin >> a >> b;
a = "a" + a;
b = "a" + b;
cout << Levenshtein_Distance(a, b);
}