Java动态规划写编辑距离,并记录过程。代码加上注释
时间: 2023-05-15 22:06:58 浏览: 69
当然可以,以下是Java动态规划写编辑距离的代码,注释也已经加上了:
public class EditDistance {
public static void main(String[] args) {
String str1 = "kitten";
String str2 = "sitting";
int result = editDistance(str1, str2);
System.out.println("编辑距离为:" + result);
}
public static int editDistance(String str1, String str2) {
int len1 = str1.length();
int len2 = str2.length();
int[][] dp = new int[len1 + 1][len2 + 1]; // dp数组记录编辑距离
// 初始化dp数组
for (int i = 0; i <= len1; i++) {
dp[i][0] = i;
}
for (int j = 0; j <= len2; j++) {
dp[0][j] = j;
}
// 动态规划求解编辑距离
for (int i = 1; i <= len1; i++) {
for (int j = 1; j <= len2; 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], Math.min(dp[i][j - 1], dp[i - 1][j - 1])) + 1;
}
}
}
// 输出编辑距离过程
int i = len1;
int j = len2;
while (i > 0 && j > 0) {
if (str1.charAt(i - 1) == str2.charAt(j - 1)) {
i--;
j--;
} else {
if (dp[i][j] == dp[i - 1][j - 1] + 1) {
System.out.println("将 " + str1.charAt(i - 1) + " 替换为 " + str2.charAt(j - 1));
i--;
j--;
} else if (dp[i][j] == dp[i - 1][j] + 1) {
System.out.println("删除 " + str1.charAt(i - 1));
i--;
} else if (dp[i][j] == dp[i][j - 1] + 1) {
System.out.println("插入 " + str2.charAt(j - 1));
j--;
}
}
}
return dp[len1][len2];
}
}
希望这个代码能够帮到你!