给定两个字符串 AA 和 BB,现在要将 AA 经过若干操作变为 BB,可进行的操作有:
- 删除–将字符串 AA 中的某个字符删除。
- 插入–在字符串 AA 的某个位置插入某个字符。
- 替换–将字符串 AA 中的某个字符替换为另一个字符。
现在请你求出,将 AA 变为 BB 至少需要进行多少次操作。
输入格式
第一行包含整数 nn,表示字符串 AA 的长度。
第二行包含一个长度为 nn 的字符串 AA。
第三行包含整数 mm,表示字符串 BB 的长度。
第四行包含一个长度为 mm 的字符串 BB。
字符串中均只包含大小写字母。
输出格式
输出一个整数,表示最少操作次数。
数据范围
1≤n,m≤10001≤n,m≤1000
输入样例:
10
AGTCTGACGC
11
AGTAAGTAGGC
输出样例:
4
思路:
作为经典DP问题,这一题也是用闫氏DP分析法。
1.状态表示:
集合:将字符串A的前i位变成字符串B的前j位的操作方式(f[i][j])
属性:操作数量最小值
2.状态计算:
第一种情况,删除。如果需要删除,就说明A字符串的第i位删掉后,能和字符串B完全匹配。而A的前i-1位与B的j为相匹配的操作次数为f[i-1][j],在这个基础上加一次操作数量就是f[i][j]。
第二种情况,增加。与第一种情况类似,但是A是比B少一位。因此A的前i位与B的前j-1位是完全匹配的。(f[i][j-1])在这个基础上加一就是f[i][j]。
第三种情况,替换。这种情况也需要分类讨论:1.如果A的第i位与B第j位相同,则不用调换,那么f[i][j]就等于f[i-1][j-1].2.如果不相同,那么就是f[i-1][j-1]+1,因为A前i-1和B前j-1肯定是完全匹配的。
在代码中还要记得初始化i或j为0的情况,如f[i][0]就是i要删除全部i位,就初始化为i。而f[0][j]就是要增加j位,因此初始化为j。
那么,代码就是:
int leastEdit(string a, string b){int m = a.size(), n = b.size();vector<vector<int>> dp(m+1, vector<int>(n+1));for(int i = 0; i <= m; i++) dp[i][0] = i;for(int i = 0; i <= n; i++) dp[0][i] = i;for(int i = 1; i <= m; i++){for(int j = 1; j <= n; j++){dp[i][j] = min(dp[i][j - 1], dp[i - 1][j]) + 1; // 添加 和 删除 dp[i][j] = min(dp[i][j], dp[i-1][j-1] + (a[i - 1] != b[j - 1])); // 替换和 啥也不做}}return dp[m][n];
}作者:jasonlin
链接:https://www.acwing.com/solution/content/10499/
来源:AcWing
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。