题目描述:
给定两个字符串str1和str2,再给定三个整数ic,dc,rc,分别代表插入、删除、替换一个字符的代价,返回将str1编辑成str2的最小代价。
举例:
str1="abc" str2="adc" ic=5 dc=3 rc=2,从"abc"编辑到"adc"把b替换成d代价最小,为2;
str1="abc" str2="adc" ic=5 dc=3 rc=10,从"abc"编辑到"adc",先删除b再插入d代价最小,为8;
/*
* 首先生成M+1,N+1的dp矩阵,dp[i][j]代表str1[0...i-1]编辑成str2[0...j-1]的最小代价。
* dp矩阵计算过程如下:
* 1.dp[0][0]=0,表示str1空子串编辑成str2空子串的代价为0;
* 2.矩阵dp第一列dp[0...M-1][0],dp[i][0]表示str1[0...i-1]编辑成空串的最小代价,
* 即将str1[0...i-1]所有的字符删掉的代价,dp[i][0]=dc*i;
* 3.矩阵dp第一行dp[0][0...N-1],dp[0][j]表示将空串编辑成str2[0...j-1]的最小代价,
* 即在空串里插入str2[0...j-1]所有字符的代价,dp[0][j]=ic*j;
* 4.其他位置按照从左到右,从上到下来计算dp值,有以下四种情况:
* a.str1[0...i-1]可以先编辑成str1[0...i-2],也就是删除str1[i-1],然后由str1[0...i-2]编辑成str2[0...j-1],
* dp[i-1][j]表示str1[0...i-2]编辑成str2[0...j-1]的代价,所以,dp[i][j]=dc+dp[i-1][j];
* b.str1[0...i-1]可以先编辑成str2[0...j-2],然后将str2[0...j-2]插入字符str2[j-1],编辑成str2[0...j-1],
* dp[i][j-1]表示将str1[0...i-1]编辑成str2[0...j-2]的代价,所以,dp[i][j]=dp[i][j-1]+ic;
* c.如果str1[i-1]!=str2[j-1],先将str1[0...i-2]编辑成str2[0...j-2],然后将str1[i-1]替换为str2[j-1],
* dp[i-1][j-1]表示将str1[0...i-2]编辑成str2[0...j-2]的代价,所以,dp[i][j]=dp[i-1][j-1]+rc;
* d.如果str1[i-1]==str2[j-1],先将str1[0...i-2]编辑成str2[0...j-2],因为str1[i-1]==str2[j-1],
* dp[i-1][j-1]表示将str1[0...i-2]编辑成str2[0...j-2]的代价,所以,dp[i][j]=dp[i-1][j-1]+rc;
* 以上四种情况,取最小值为dp[i][j]
*
* 通过空间压缩,可以将空间复杂度压缩到N+1
*/
public class 最小编辑代价 { public static int minCost1(String str1, String str2, int ic, int dc, int rc) { if (str1 == null || str2 == null) { return 0; } char[] chs1 = str1.toCharArray(); char[] chs2 = str2.toCharArray(); int row = chs1.length + 1; int col = chs2.length + 1; int[][] dp = new int[row][col]; for (int i = 1; i < row; i++) { dp[i][0] = dc * i; } for (int j = 1; j < col; j++) { dp[0][j] = ic * j; } for (int i = 1; i < row; i++) { for (int j = 1; j < col; j++) { if (chs1[i - 1] == chs2[j - 1]) { dp[i][j] = dp[i - 1][j - 1]; } else { dp[i][j] = dp[i - 1][j - 1] + rc; } dp[i][j] = Math.min(dp[i][j], dp[i][j - 1] + ic); dp[i][j] = Math.min(dp[i][j], dp[i - 1][j] + dc); } } return dp[row - 1][col - 1]; } public static int minCost2(String str1, String str2, int ic, int dc, int rc) { if (str1 == null || str2 == null) { return 0; } char[] chs1 = str1.toCharArray(); char[] chs2 = str2.toCharArray(); char[] longs = chs1.length >= chs2.length ? chs1 : chs2; char[] shorts = chs1.length < chs2.length ? chs1 : chs2; if (chs1.length < chs2.length) { // str2较长就交换ic和dc的值 int tmp = ic; ic = dc; dc = tmp; } int[] dp = new int[shorts.length + 1]; for (int i = 1; i <= shorts.length; i++) { dp[i] = ic * i; } for (int i = 1; i <= longs.length; i++) { int pre = dp[0]; // pre表示左上角的值 dp[0] = dc * i; for (int j = 1; j <= shorts.length; j++) { int tmp = dp[j]; // dp[j]没更新前先保存下来 if (longs[i - 1] == shorts[j - 1]) { dp[j] = pre; } else { dp[j] = pre + rc; } dp[j] = Math.min(dp[j], dp[j - 1] + ic); dp[j] = Math.min(dp[j], tmp + dc); pre = tmp; // pre变成dp[j]没更新前的值 } } return dp[shorts.length]; } public static void main(String[] args) { String str1 = "ab12cd3"; String str2 = "abcdf"; System.out.println(minCost1(str1, str2, 5, 3, 2)); System.out.println(minCost2(str1, str2, 5, 3, 2)); str1 = "abcdf"; str2 = "ab12cd3"; System.out.println(minCost1(str1, str2, 3, 2, 4)); System.out.println(minCost2(str1, str2, 3, 2, 4)); str1 = ""; str2 = "ab12cd3"; System.out.println(minCost1(str1, str2, 1, 7, 5)); System.out.println(minCost2(str1, str2, 1, 7, 5)); str1 = "abcdf"; str2 = ""; System.out.println(minCost1(str1, str2, 2, 9, 8)); System.out.println(minCost2(str1, str2, 2, 9, 8)); } }