题目描述
小施和小唐两个同学近来对字符串操作很感兴趣。小施和小唐各自给了一个字符串,分别记作S和T。如果能通过魔法转换使小施的串和小唐的串变成同一个,那么他们两个人都会很开心。这里的魔法指的是小施的串可以任意删掉某个字符或者替换某个字符。通过这两种方式。如将401变为415,可通过将401中的1替换为5得405,然后将0替换为1得415,需2次修改。
现在给定长度至多为200的两个字符串S和T,你的任务是计算将字符串S变为字符串T的删除和替换的最少总次数。
输入
每组有2行,每行上有1个长度不超过200的字符串,字符串中不含空格。
输出
对输入中的每组测试数据,求出该组中第一行的字符串变为第二行的字符串B所需的删除与替换的最少总次数。
样例输入
输入样例1
32134
23
输入样例2
43010
4014
样例输出
输出样例1
3
输出样例2
2
关于#删除与替换#的问题,如何解决?
- 写回答
- 好问题 0 提建议
- 追加酬金
- 关注问题
- 邀请回答
-
3条回答 默认 最新
- 投三分的金闪闪 2022-06-05 15:11关注
计算一个字符串变为另一个字符串的最少总次数,望采纳
public int minDistance(String word1, String word2) { int n = word1.length(); int m = word2.length(); // 有一个字符串为空串 if (n * m == 0) { return n + m; } // DP 数组 int[][] D = new int[n + 1][m + 1]; // 边界状态初始化 for (int i = 0; i < n + 1; i++) { D[i][0] = i; } for (int j = 0; j < m + 1; j++) { D[0][j] = j; } // 计算所有 DP 值 for (int i = 1; i < n + 1; i++) { for (int j = 1; j < m + 1; j++) { int left = D[i - 1][j] + 1; int down = D[i][j - 1] + 1; int left_down = D[i - 1][j - 1]; if (word1.charAt(i - 1) != word2.charAt(j - 1)) { left_down += 1; } D[i][j] = Math.min(left, Math.min(down, left_down)); } } return D[n][m]; }
本回答被题主选为最佳回答 , 对您是否有帮助呢?解决 1无用
悬赏问题
- ¥20 基于MSP430f5529的MPU6050驱动,求出欧拉角
- ¥20 Java-Oj-桌布的计算
- ¥15 powerbuilder中的datawindow数据整合到新的DataWindow
- ¥20 有人知道这种图怎么画吗?
- ¥15 pyqt6如何引用qrc文件加载里面的的资源
- ¥15 安卓JNI项目使用lua上的问题
- ¥20 RL+GNN解决人员排班问题时梯度消失
- ¥60 要数控稳压电源测试数据
- ¥15 能帮我写下这个编程吗
- ¥15 ikuai客户端l2tp协议链接报终止15信号和无法将p.p.p6转换为我的l2tp线路