字符串的修改

1225: 字符串的修改

描述

题目描述：

设A和B是两个字符串。我们要用最少的字符操作次数，将字符串A转换为字符串B。这里所说的字符操作共有三种：  1. 删除一个字符；  2. 插入一个字符；  3. 将一个字符改为另一个字符。  对任给的两个字符串A和B，计算出将字符串A变换为字符串B所用的最少字符操作次数。

输入：

第一行为字符串A；第二行为字符串B；字符串A和B的长度均小于200。

输出：

只有一个正整数，为最少字符操作次数。

样例输入 sfdxbqwgfdgw 样例输出 4 思路：找两个字符串相同字母的个数，这里找的时候需要注意，必须按照从前到后的顺序找，假如前一个字母在二串中的第3个位置找到了，那么第二个字母必须 从第4个位置开始查找。 找到相同个个数的字符后，二串的长度减去相同的字符个数就是剩下需要替换的字符个数，然后再加上两个串长度的差的绝对值，这里是因为没有说哪个串比较长 哪个比较短，所以需要加绝对值，长度差即为要进行的删除操作。 贴代码 #include<bits/stdc++.h> using namespace std; int main() { string s1,s2,s3; int samenum = 0; cin>>s1>>s2; int flag=0; for(int i=0;i<s2.size();i++) { for(int j=flag;j<s1.size();j++) { if(s2[i] == s1[j]) { flag = j; samenum ++; break; } } } int sum = s2.size() - samenum + abs(s1.size() - s2.size()); cout<<sum; return 0; }