解题思路:
动态规划,dp[][]这里注意一下行列的含义,我们要比对的是str1和str2,所以dp[str1][str2]
当然暴力匹配也是可以的,但不是最优解,还有贪心算法,但也不是最优解
注意事项:
参考代码:
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
//用一个distances待会存放距离。
List<Integer> distances = new ArrayList<>();
//输入n次循环,进到循环里面开始输入每一次的str1和str2,在循环里面调用calculateDistance方法
//这里calculateDistance务必要返回一个int值,不然到时候打印答案的时候不好处理,把distance放进容器里
for (int i = 0; i < n; i++) {
String str1 = sc.next();
String str2 = sc.next();
int distance = calculateDistance(str1, str2);
distances.add(distance);
}
for (int distance : distances) { //强循环,将distances里面的每个值赋给distance,然后打印出来
System.out.println(distance);
}
}
public static int calculateDistance(String str1, String str2) {
//这里初始化数组的时候要注意长度+1
int[][] dp = new int[str1.length() + 1][str2.length() + 1];
for (int i = 0; i <= str1.length(); i++) {
dp[i][0] = i;
}
for (int j = 0; j <= str2.length(); j++) {
dp[0][j] = j;
}
//从数组的第二行第二列开始比较 (dp[0][0]=0)
//如果str1[0]==str2[0] 那么dp[1][1]=dp[0][0] 即=0;
//如果str1[0]!=str2[0] 那么比较上一次的dp+1的情况和str1与str2哪个数组+1。谁最小
for (int i = 1; i <= str1.length(); i++) {
for (int j = 1; j <= str2.length(); j++) {
if (str1.charAt(i - 1) == str2.charAt(j - 1)) {
dp[i][j] = dp[i - 1][j - 1];
} else {
dp[i][j] = Math.min(dp[i - 1][j - 1] + 1, Math.min(dp[i][j - 1] + 1, dp[i - 1][j] + 1));
}
}
}
return dp[str1.length()][str2.length()];
}
}
0.0分
0 人评分
矩形面积交 (C语言代码)浏览:1493 |
C语言程序设计教程(第三版)课后习题5.7 (C++代码)浏览:834 |
C语言程序设计教程(第三版)课后习题10.4 (C语言代码)浏览:663 |
ASCII帮了大忙浏览:740 |
printf基础练习2 (有点不明白)浏览:823 |
2005年春浙江省计算机等级考试二级C 编程题(1) (C语言代码)浏览:571 |
C语言程序设计教程(第三版)课后习题5.4 (C语言代码)浏览:729 |
C语言程序设计教程(第三版)课后习题5.4 (C语言代码)浏览:551 |
C语言程序设计教程(第三版)课后习题5.5 (C语言代码)浏览:551 |
核桃的数量 (C语言代码)浏览:869 |