#include <iostream>
#include <string>
using namespace std;
/*
动态规划
思路:arr[i][j]表示A的i的字母和B的j字母之间的间距。A字符串用arr[i][0]表示,间距arr[i-1][j] + 1;
B字符串用arr[0][j]表示,间距用arr[i][j-1] + 1;A与B组层一个二维数组arr[i-1][j-1],查看A与B的字母不相等,则累加arr[i-1][j-1]+ = 1;
比较他们最小间距。
三种操作:
一,在单词A插入一个字符;
二,在单词B插入一个字符;
三,修改单词A的一个字符;
如果A与B的字符相同,则不需要进行;如果A与B不相同,则查看
*/
int MinDistance(string firstStr, string secondStr)
{
int n = firstStr.size();
int m = secondStr.size();
int arr[n+1][m+1];
//A或B单词为空
if (n*m == 0) {
return n*m;
}
//A单词删除或插入
for (int i = 0 ; i < n+1; i++) {
arr[i][0] = i;
}
//B单词, 删除B或插入A
for (int j = 0 ; j < m+1; j++) {
arr[0][j] = j;
}
//循环查找
for (int i = 1; i < n+1; i++) {
for (int j = 1; j < m+1; j++) {
int left = arr[i-1][j] + 1; //左, 第一个字符串的1个间距
int down = arr[i][j-1] + 1; //右,第二个字符串的1个间距
int leftDown = arr[i-1][j-1];
if (firstStr[i-1] != secondStr[j-1]) { //比较第一个字符与第二个字符
leftDown += 1; // 查看他们间距
}
arr[i][j] = min(left, min(down, leftDown)); //获取最小间距
}
}
return arr[n][m];
}
int main()
{
string firstStr, secondStr;
while(cin>>firstStr>>secondStr) {
cout<<MinDistance(firstStr, secondStr)<<endl;
}
}